A subclass of Horn CNFs optimally compressible in polynomial time

The problem of Horn Minimization (HM) can be stated as follows: given a Horn CNF representing a Boolean function f, find a shortest possible (optimally compressed) CNF representation of f, i.e., a CNF representation of f which consists of the minimum possible number of clauses. This problem is the formalization of the problem of knowledge compression for speeding up queries to propositional Horn expert systems, and it is known to be NP-hard. There are two subclasses of Horn functions for which HM is known to be solvable in polynomial time: acyclic and quasi-acyclic Horn functions. In this paper we define a new class of Horn functions properly containing both of the known classes and design a polynomial time HM algorithm for this new class.     

Error-Free and Best-Fit Extensions of Partially Defined Boolean Functions

In this paper, we address a fundamental problem related to the induction of Boolean logic: Given a set of data, represented as a set of binary “truen-vectors” (or “positive examples”) and a set of “falsen-vectors” (or “negative examples”), we establish a Boolean function (or an extension)f, so thatfis true (resp., false) in every given true (resp., false) vector. We shall further require that such an extension belongs to a certain specified class of functions, e.g., class of positive functions, class of Horn functions, and so on. The class of functions represents our a priori knowledge or hypothesis about the extensionf, which may be obtained from experience or from the analysis of mechanisms that may or may not cause the phenomena under consideration. The real-world data may contain errors, e.g., measurement and classification errors might come in when obtaining data, or there may be some other influential factors not represented as variables in the vectors. In such situations, we have to give up the goal of establishing an extension that is perfectly consistent with the given data, and we are satisfied with an extensionfhaving the minimum number of misclassifications. Both problems, i.e., the problem of finding an extension within a specified class of Boolean functions and the problem of finding a minimum error extension in that class, will be extensively studied in this paper. For certain classes we shall provide polynomial algorithms, and for other cases we prove their NP-hardness.     

Decision lists and related Boolean functions

We consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1-decision lists has interesting relationships to independently defined classes such as disguised Horn functions, read-once functions, nested differences of concepts, threshold functions, and 2-monotonic functions. In particular, 1-decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1-decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.     

On renamable Horn and generalized Horn functions

A Boolean function in disjunctive normal form (DNF) is aHorn function if each of its elementary conjunctions involves at most one complemented variable. Ageneralized Horn function is constructed from a Horn function by disjuncting a nested set of complemented variables to it. The satisfiability problem is solvable in polynomial time for both Horn and generalized Horn functions. A Boolean function in DNF is said to berenamable Horn if it is Horn after complementation of some variables. Succinct mathematical characterizations and linear-time algorithms for recognizing renamable Horn and generalized Horn functions are given in this paper. The algorithm for recognizing renamable Horn functions gives a new method to test 2-SAT. Some computational results are also given.The authors were supported in part by the Office of Naval Research under University Research Initiative grant number N00014-86-K-0689. Chandru was also supported by NSF grant number DMC 88-07550.The authors gratefully acknowledge the partial support of NSF (Grant DMS 89-06870) and AFOSR (Grant 89-0066 and 89-0512).     

Recognition of interval Boolean functions

Interval functions constitute a special class of Boolean functions for which it is very easy and fast to determine their functional value on a specified input vector. The value of an n-variable interval function specified by interval [a,b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a,b]. In this paper we study the problem of deciding whether a given disjunctive normal form represents an interval function and if so then we also want to output the corresponding interval. For general Boolean functions this problem is co-NP-hard. In our article we present a polynomial time algorithm which works for monotone functions. We shall also show that given a Boolean function f belonging to some class which is closed under partial assignment and for which we are able to solve the satisfiability problem in polynomial time, we can also decide whether f is an interval function in polynomial time. We show how to recognize a “renamable” variant of interval functions, i.e., their variable complementation closure. Another studied problem is the problem of finding an interval extension of partially defined Boolean functions. We also study some other properties of interval functions.      

Horn minimization by iterative decomposition

Given a Horn CNF representing a Boolean function f, the problem of Horn minimization consists in constructing a CNF representation off which has a minimum possible number of clauses. This problem is the formalization of the problem of knowledge compression for speeding up queries to propositional Horn expert systems, and it is known to be NP-hard. In this paper we present a linear time algorithm which takes a Horn CNF as an input, and through a series of decompositions reduces the minimization of the input CNF to the minimization problem on a“shorter” CNF. The correctness of this decomposition algorithm rests on several interesting properties of Horn functions which, as we prove here, turn out to be independent of the particular CNF representations. This revised version was published online in June 2006 with corrections to the Cover Date.     

Recognition and dualization of disguised bidual Horn functions

We consider the problem of dualizing a Boolean function f given by CNF, i.e., computing a CNF for its dual f^d. While this problem is not solvable in quasi-polynomial total time in general (unless SAT is solvable in quasi-polynomial time), it is so in case the input belongs to special classes, e.g., the class of bidual Horn CNF ? [Discrete Appl. Math. 96-97 (1999) 55-88] (i.e., both ? and its dual ?^d represent Horn functions). In this paper, we show that a disguised bidual Horn CNF ? (i.e., ? becomes a bidual Horn CNF after renaming of variables) can be recognized in polynomial time, and its dualization can be done in quasi-polynomial total time. We also establish a similar result for dualization of prime CNFs.     

The Complexity of Deciding if a Boolean Function Can Be Computed by Circuits over a Restricted Basis

We study the complexity of the following algorithmic problem: Given a Boolean function f and a finite set of Boolean functions B, decide if there is a circuit with basis B that computes f. We show that if both f and all functions in B are given by their truth-table, the problem is in quasipolynomial-size AC⁰, and thus cannot be hard for AC⁰(2) or any superclass like NC¹, L, or NL. This answers an open question by Bergman and Slutzki (SIAM J. Comput., 2000). Furthermore we show that, if the input functions are not given by their truth-table but in a succinct way, i.e., by circuits (over any complete basis), the above problem becomes complete for the class coNP. Supported in part by DFG Grant Vo 630/5-2 and EPSRC Grant 531174.     

On P versus NP $ \cap $ co-NP for decision trees and read-once branching programs

It is known that if a Boolean function f in n variables has a DNF and a CNF of size then f also has a (deterministic) decision tree of size exp(O(log n log² N)). We show that this simulation cannot be made polynomial: we exhibit explicit Boolean functions f that require deterministic trees of size exp where N is the total number of monomials in minimal DNFs for f and ?f. Moreover, we exhibit new examples of explicit Boolean functions that require deterministic read-once branching programs of exponential size whereas both the functions and their negations have small nondeterministic read-once branching programs. One example results from the Bruen—Blokhuis bound on the size of nontrivial blocking sets in projective planes: it is remarkably simple and combinatorially clear. Other examples have the additional property that f is in AC⁰. Received: June 5 1997.     

The equivalence of Horn and network complexity for Boolean functions

Summary We propose in this paper a logical complexity measure — Horn complexity — for Boolean functions which measures the minimal length of quasi-Horn definitions of such functions by propositional formulae. The interest for this complexity measure comes on the one hand from the observation that the satisfiability problem for Horn formulae is in P, on the other hand from a strong connection to Cook's problem. We show the proposed Horn complexity to be polynomially equivalent to network complexity and therefore to Turing complexity for Boolean functions.A preliminary version of this work has appeared in the Proceedings of the 5^th Scandinavian Logic Symposium, edited by B. Mayoh and F. Jensen, Aalborg University Press, Aalborg 1979     

Disjoint essential sets of implicates of a CQ Horn function

In this paper we study a class of CQ Horn functions introduced in Boros et al. (Ann Math Artif Intell 57(3–4):249–291, 2010). We prove that given a CQ Horn function f, the maximal number of pairwise disjoint essential sets of implicates of f equals the minimum number of clauses in a CNF representing f. In other words, we prove that the maximum number of pairwise disjoint essential sets of implicates of f constitutes a tight lower bound on the size (the number of clauses) of any CNF representation of f.     

New Results on Noncommutative and Commutative Polynomial Identity Testing

Using ideas from automata theory, we design the first polynomial deterministic identity testing algorithm for the sparse noncommutative polynomial identity testing problem. Given a noncommuting black-box polynomial f ? \mathbb F{x₁,?,x_n}f \in {\mathbb F}\{x_{1},\ldots,x_n\} of degree d with at most t monomials, where the variables x_i are noncommuting, we give a deterministic polynomial identity test that checks if C o 0C \equiv 0 and runs in time polynomial in d, n, |C|, and t. Our algorithm evaluates the black-box polynomial for x_i assigned to matrices over \mathbbF{\mathbb{F}} and, in fact, reconstructs the entire polynomial f in time polynomial in n, d and t.     

Compact DSOP and Partial DSOP Forms

Given a Boolean function f on n variables, a Disjoint Sum-of-Products (DSOP) of f is a set of products (ANDs) of subsets of literals whose sum (OR) equals f, such that no two products cover the same minterm of f. DSOP forms are a special instance of partial DSOPs, i.e. the general case where a subset of minterms must be covered exactly once and the other minterms (typically corresponding to don’t care conditions of f) can be covered any number of times. We discuss finding DSOPs and partial DSOPs with a minimal number of products, a problem theoretically connected with various properties of Boolean functions and practically relevant in the synthesis of digital circuits. Finding an absolute minimum is hard, in fact we prove that the problem of absolute minimization of partial DSOPs is NP-hard. Therefore it is crucial to devise a polynomial time heuristic that compares favorably with the known minimization tools. To this end we develop a further piece of theory starting from the definition of the weight of a cube c as a functions of the number of fragments induced on other cubes by the selection of c, and show how cube weights can be exploited for building a class of minimization heuristics for DSOP and partial DSOP synthesis. A set of experiments conducted on major benchmark functions show that our method, with a family of variants, always generates better results than the ones of previous heuristics, including the method based on a BDD representation of f.     

Gain–bandwidth limitations of microwave transistor

This work enables one to obtain the potential gain (G_T) characteristics with the associated source (Z_S) and load (Z_L) termination functions, depending upon the input mismatching (V_i), noise (F), and the device operation parameters, which are the configuration type (CT), bias conditions (V_DS, I_DS), and operation frequency (f). All these functions can straightforwardly provide the following main properties of the device for use in the design of microwave amplifiers with optimum performance: the extremum gain functions (G_{T max}, G_{T min}) and their associated Z_S, Z_L terminations for the V_i and F couple and the CT, V_DS, I_DS, and f operation parameters of the device point by point; all the compatible performance (F, voltage–standing wave ratio V_i, G_T) triplets within the physical limits of the device, which are F ≥ F_min, V_i ≥ 1, G_{T min} ≤ G_T ≤ G_{T max}, together with their Z_S, Z_L termination functions; and the potential operation frequency bandwidth for a selected performance (F, V_i, G_T) triplet. The selected performance triplet and termination functions can be realized together with their potential operation bandwidth using the novel amplifier design techniques. Many examples are presented for the potential gain characteristics of the chosen low‐noise or ordinary types of transistor. © 2002 Wiley Periodicals, Inc. Int J RF and Microwave CAE 12, 483–495, 2002. Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mmce.10049     

The Complexity of Boolean Functions in Different Characteristics

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}ⁿ → {0, 1} which depend on all n variables, and distinct primes p, q:

Filter theory of BL algebras

In this paper we consider fundamental properties of some types of filters (Boolean, positive implicative, implicative and fantastic filters) of BL algebras defined in Haveshki et al. (Soft Comput 10:657–664, 2006) and Turunen (Arch Math Logic 40:467–473, 2001). It is proved in Haveshki et al. (2006) that if F is a maximal and (positive) implicative filter then it is a Boolean filter. In that paper there is an open problem Under what condition are Boolean filters positive implicative filters? One of our results gives an answer to the problem, that is, we need no more conditions. Moreover, we give simple characterizations of those filters by an identity form ? x, y(t(x, y) ∈ F), where t(x, y) is a term containing x, y.      

Translation among CNFs, characteristic models and ordered binary decision diagrams

We consider translation among conjunctive normal forms (CNFs), characteristic models, and ordered binary decision diagrams (OBDDs) of Boolean functions. It is shown in this paper that Horn OBDDs can be translated into their Horn CNFs in polynomial time. As for the opposite direction, the problem can be solved in polynomial time if the ordering of variables in the resulting OBDD is specified as an input. In case that such ordering is not specified and the resulting OBDD must be of minimum size, its decision version becomes NP-complete. Similar results are also obtained for the translation in both directions between characteristic models and OBDDs. We emphasize here that the above results hold on any class of functions having a basis of polynomial size.     

Planar acyclic computation

This paper considers the following problem: given a specification consisting of a set of variables X, a multiset of functions F on those variables, and a cyclic ordering on X F, determine whether or not there exists a planar acyclic circuit which realizes the specification. An algorithm is given which produces such a circuit whenever one exists. In proving that our algorithm meets this requirement we provide some simple mathematical characterizations of those specifications which are realizable.     

Boolean sets and most general solutions of Boolean equations

The aim of this paper is twofold. First we determine the most general form of the subsumptive general solution of a Boolean equation (Theorem 1 and Theorem 2). Then we discuss several characterizations of Boolean sets, meaning sets of zeros of Boolean functions, and prove that every Boolean transformation X=Φ(T) is the parametric general solution of a certain Boolean equation.     

The global avalanche characteristics of two Boolean functions and algebraic immunity

The global avalanche characteristics criterion of two Boolean functions was introduced by Zhou et al. [On the global avalanche characteristics criterion of two Boolean functions and the higher order nonlinearity, Inform. Sci. 180(2) (2010), pp. 256–265] to measure the cryptographic behaviour in a global characteristic. The two indicators σ _{f, g} and Δ _{f, g} of Boolean functions f and g were presented. In this paper, a new upper bound on σ _{f, g} is derived, and a technique on constructing Boolean functions to attain the lower bound on the sum-of-squares indicator is described by using the disjoint spectra method. Some new upper bounds on Δ _{f, g} and σ _{f, g} are deduced for two special Boolean functions. Two relationships between σ _{f, g} and algebraic immunity of the two Boolean functions are obtained. Finally, some links among different cryptographic indicators are shown.