Boolean functions with a simple certificate for CNF complexity

In this paper we study relationships between CNF representations of a given Boolean function $f$ and essential sets of implicates of $f$. It is known that every CNF representation and every essential set must intersect. Therefore the maximum number of pairwise disjoint essential sets of $f$ provides a lower bound on the size of any CNF representation of $f$. We are interested in functions, for which this lower bound is tight, and call such functions coverable. We prove that for every coverable function there exists a polynomially verifiable certificate (witness) for its minimum CNF size. On the other hand, we show that not all functions are coverable, and construct examples of non-coverable functions. Moreover, we prove that computing the lower bound, i.e. the maximum number of pairwise disjoint essential sets, is $NP$-hard under various restrictions on the function and on its input representation.     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

P-chaos implies distributional chaos and chaos in the sense of Devaney with positive topological entropy

Let f be a continuous map from a compact metric space X to itself. The map f is called to be P-chaotic if it has the pseudo-orbit-tracing property and the closure of the set of all periodic points for f is equal to X. We show that every P-chaotic map from a continuum to itself is chaotic in the sense of Devaney and exhibits distributional chaos of type 1 with positive topological entropy.     

Strict lower semicontinuity of the level sets and invexity of a locally Lipschitz function

The strict lower semicontinuity property (slsc property) of the level sets of a real-valued functionf defined on a subsetCR ⁿ was introduced by Zang, Choo, and Avriel (Ref. 1). They showed a class of functions for which the slsc property is equivalent to invexity, i.e., the statement that every stationary point off overC is a global minimum. In this paper, we study the relationship between the slsc property of the level sets and invexity for another class of functions. Namely, we consider the class formed by all locally Lipschitz real-valued functions defined on an open set containingC. For these functions, invexity implies the slsc property of the level sets, but not conversely.The authors would like to thank Dr. B. D. Craven and the referees for helpful comments and suggestions.     

On extended algebraic immunity

Algebraic immunity (AI) measures the resistance of a Boolean function f against algebraic attack. Extended algebraic immunity (EAI) extends the concept of algebraic immunity, whose point is that a Boolean function f may be replaced by another Boolean function f ^c called the algebraic complement of f. In this paper, we study the relation between different properties (such as weight, nonlinearity, etc.) of Boolean function f and its algebraic complement f ^c . For example, the relation between annihilator sets of f and f ^c provides a faster way to find their annihilators than previous report. Next, we present a necessary condition for Boolean functions to be of the maximum possible extended algebraic immunity. We also analyze some Boolean functions with maximum possible algebraic immunity constructed by known existing construction methods for their extended algebraic immunity.     

Homomorphism-Homogeneous Partially Ordered Sets

A structure is called homogeneous if every isomorphism between finite substructures of the structure extends to an automorphism of the structure. Recently, P. J. Cameron and J. Nešetřil introduced a relaxed version of homogeneity: we say that a structure is homomorphism-homogeneous if every homomorphism between finite substructures of the structure extends to an endomorphism of the structure. In this paper we characterize homomorphism-homogeneous partially ordered sets (where a homomorphism between partially ordered sets A and B is a mapping f : A →B satisfying ). We show that there are five types of homomorphism-homogeneous partially ordered sets: partially ordered sets whose connected components are chains; trees; dual trees; partially ordered sets which split into a tree and a dual tree; and X ₅-dense locally bounded partially ordered sets. Supported by the Ministry od Science and Environmental Protection of the Republic of Serbia, Grant No. 144017.     

Seminormality properties of convex sets

In discussing Lagrange problems of optimal control for simple as well as for multiple integrals Cesari has introduced an upper semicontinuity property of variable sets called property (Q) which plays a role analogous to that of Tonelli's and McShane's concept, of seminormality for free problems of the calculus of variations. This paper deals with analytical criteria for property (Q) which is the unifying idea in the study of lower semicontinuity and lower closure with unbounded controls. In section 1 we state the concepts of seminormality, normality, and property (Q). In section 2 we establish new criteria for property (Q) in the particular situation whenf ₀(t,x,u) is continuous and seminormal (or normal) andf(t,x,u) is linear in the variableu. In section 3 we consider the role of property (Q) for restricted sets. In section 4 we discuss the intermediate properties (Q _p).     

Characterizations of strictly convex sets by the uniqueness of support points

Abstract

This short paper characterizes strictly convex sets by the uniqueness of support points (such points are called unique support points or exposed points) under appropriate assumptions. A class of so-called regular sets, for which every extreme point is a unique support point, is introduced. Closed strictly convex sets and their intersections with some other sets are shown to belong to this class. The obtained characterizations are then applied to set-valued maps and to the separation of a convex set and a strictly convex set. Under suitable assumptions, so-called set-valued maps with path property are characterized by strictly convex images of the considered set-valued map.     

An Efficient Algorithm for the Complex Roots Problem

Given a univariate polynomialf(z) of degreenwith complex coefficients, whose norms are less than 2^min magnitude, the root problem is to find all the roots off(z) up to specified precision 2^−μ. Assuming the arithmetic model for computation, we provide an algorithm which has complexityO(nlog⁵nlogB), whereb= χ + μ, and χ = max{n,m}. This improves on the previous best known algorithm of Pan for the problem, which has complexityO(n²log²nlog(m+ μ)). A remarkable property of our algorithm is that it does not require any assumptions about the root separation off, which were either explicitly, or implicitly, required by previous algorithms. Moreover it also has a work-efficient parallel implementation. We also show that both the sequential and parallel implementations of the algorithm work without modification in the Boolean model of arithmetic. In this case, it follows from root perturbation estimates that we need only specify θ = ⌈n(B+ logn+ 3)⌉ bits of the binary representations of the real and imaginary parts of each of the coefficients off. We also show that by appropriate rounding of intermediate values, we can bound the number of bits required to represent all complex numbers occurring as intermediate quantities in the computation. The result is that we can restrict the numbers we use in every basic arithmetic operation to those having real and imaginary parts with at most φ bits, where[formula]and[formula]Thus, in the Boolean model, the overall work complexity of the algorithm is only increased by a multiplicative factor ofM(φ) (whereM(ψ) =O(ψ(log ψ) log log ψ) is the bit complexity for multiplication of integers of length ψ). The key result on which the algorithm is based, is a new theorem of Coppersmith and Neff relating the geometric distribution of the zeros of a polynomial to the distribution of the zeros of its high order derivatives. We also introduce several new techniques (splitting sets and “centered” points) which hinge on it. We also observe that our root finding algorithm can be efficiently parallelized to run in parallel timeO(log⁶nlogB) usingnprocessors.     

Boolean inequations

In this paper we consider Boolean inequations i.e. the inequations of the form f(X)≠0, where f is a Boolean function. The basic idea in this paper is: the inequation f(X)≠0 means that there exists p such that f(X)=p and p≠0. We give the formula which determines all the solutions of Boolean inequation.     

Co-countable sets of uniqueness for series of independent random variables

Given a sequence of independent random variables (fk) on a standard Borel space Ω with probability measure μ and a measurable set F, the existence of a countable set S⊂F is shown, with the property that series k_∑ckfk which are constant on S are constant almost everywhere on F. As a consequence, if the functions fk are not constant almost everywhere, then there is a countable set S⊂Ω such that the only series k_∑ckfk which is null on S is the null series; moreover, if there exists b<1 such that for every k and every α, then the set S can be taken inside any measurable set F with μ(F)>b.     

Distance transforms for real-valued functions

A set in a metric space gives rise to its distance function that associates with every point its distance to the nearest point in the set. This function is called the distance transform of the original set. In the same vein, given a real-valued function f we consider the expected distances from any point to a level set of f taken at a random height. This produces another function called a distance transform of f. Such transforms are called grey-scale distance transforms to signpost their differences from the binary case when sets (or their indicators) give rise to conventional distance functions. Basic properties of the introduced grey-scale distance transform are discussed. The most important issue is the uniqueness problem whether two different functions may share the same distance transform. We answer this problem in a generality completely sufficient for all practical applications in imaging sciences, the full-scale problem remains open.     

k-metric spaces

In this paper, we give a new generalization of metric spaces called k-metric spaces. Our k-metrics are valued in lattice ordered groups, which allows us to talk about distance in non-abelian lattice ordered groups. We also discuss a class of (not necessarily abelian) lattice ordered groups in which every k-metric induces a topology. Then we show that every k-metric valued in the real numbers is metrizable. In the last section, we characterize intrinsic metrics on lattice ordered rings that are almost f-rings and prove that being an almost f-ring is necessary and sufficient for this characterization. Then we show that if a lattice ordered ring is representable, then every intrinsic metric is a k-metric.     

Determining Sets, Resolving Sets, and the Exchange Property

A subset U of vertices of a graph G is called a determining set if every automorphism of G is uniquely determined by its action on the vertices of U. A subset W is called a resolving set if every vertex in G is uniquely determined by its distances to the vertices of W. Determining (resolving) sets are said to have the exchange property in G if whenever S and R are minimal determining (resolving) sets for G and ${r\in R}$ , then there exists ${s\in S}$ so that ${S-\{s\} \cup \{r\}}$ is a minimal determining (resolving) set. This work examines graph families in which these sets do, or do not, have the exchange property. This paper shows that neither determining sets nor resolving sets have the exchange property in all graphs, but that both have the exchange property in trees. It also gives an infinite graph family (n-wheels where n ≥ 8) in which determining sets have the exchange property but resolving sets do not. Further, this paper provides necessary and sufficient conditions for determining sets to have the exchange property in an outerplanar graph.     

An improvement on the complexity of factoring read-once Boolean functions

Read-once functions have gained recent, renewed interest in the fields of theory and algorithms of Boolean functions, computational learning theory and logic design and verification. In an earlier paper [M.C. Golumbic, A. Mintz, U. Rotics, Factoring and recognition of read-once functions using cographs and normality, and the readability of functions associated with partial k-trees, Discrete Appl. Math. 154 (2006) 1465-1677], we presented the first polynomial-time algorithm for recognizing and factoring read-once functions, based on a classical characterization theorem of Gurvich which states that a positive Boolean function is read-once if and only if it is normal and its co-occurrence graph is P₄-free.In this note, we improve the complexity bound by showing that the method can be modified slightly, with two crucial observations, to obtain an O(n|f|) implementation, where |f| denotes the length of the DNF expression of a positive Boolean function f, and n is the number of variables in f. The previously stated bound was O(n²k), where k is the number of prime implicants of the function. In both cases, f is assumed to be given as a DNF formula consisting entirely of the prime implicants of the function.     

Density condensation of Boolean formulas

The following problem is considered: given a Boolean formula f, generate another formula g such that: (i) If f is unsatisfiable then g is also unsatisfiable. (ii) If f is satisfiable then g is also satisfiable and furthermore g is “easier” than f. For the measure of this easiness, we use the density of a formula f which is defined as (the number of satisfying assignments)/2ⁿ, where n is the number of Boolean variables of f. In this paper, we mainly consider the case that the input formula f is given as a 3-CNF formula and the output formula g may be any formula using Boolean AND, OR and negation. Two different approaches to this problem are presented: one is to obtain g by reducing the number of variables and the other by increasing the number of variables, both of which are based on existing SAT algorithms. Our performance evaluation shows that, a little surprisingly, better SAT algorithms do not always give us better density-condensation algorithms.     

On degenerate multi-row Gomory cuts

Borozan and Cornuéjols show that valid inequalities for an infinite relaxation for MIPs, relative to some vertex f of the linear relaxation, are determined by maximal lattice-free convex sets containing f. We show that cuts for the original MIP are given by such sets with f in the interior.     

Composition of Post classes and normal forms of Boolean functions

The class composition C°K of Boolean clones, being the set of composite functions f(g₁,…,g_n) with f∈C, g₁,…,g_n∈K, is investigated. This composition C°K is either the join C∨K in the Post Lattice or it is not a clone, and all pairs of clones C,K are classified accordingly.Factorizations of the clone Ω of all Boolean functions as a composition of minimal clones are described and seen to correspond to normal form representations of Boolean functions. The median normal form, arising from the factorization of Ω with the clone SM of self-dual monotone functions as the leftmost composition factor, is compared in terms of complexity with the well-known DNF, CNF, and Zhegalkin (Reed-Muller) polynomial representations, and it is shown to provide a more efficient normal form representation.     

An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation

Given a finite set V, and a hypergraph H⊆2^V, the hypergraph transversal problem calls for enumerating all minimal hitting sets (transversals) for H. This problem plays an important role in practical applications as many other problems were shown to be polynomially equivalent to it. Fredman and Khachiyan [On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms 21 (1996) 618-628] gave an incremental quasi-polynomial-time algorithm for solving the hypergraph transversal problem. In this paper, we present an efficient implementation of this algorithm. While we show that our implementation achieves the same theoretical worst-case bound, practical experience with this implementation shows that it can be substantially faster. We also show that a slight modification of the original algorithm can be used to obtain a stronger bound on the running time.More generally, we consider a monotone property π over a bounded n-dimensional integral box. As an important application of the above hypergraph transversal problem, pioneered by Bioch and Ibaraki [Complexity of identification and dualization of positive Boolean functions, Inform. and Comput. 123 (1995) 50-63], we consider the problem of incrementally generating simultaneously all minimal subsets satisfying π and all maximal subsets not satisfying π, for properties given by a polynomial-time satisfiability oracle. Problems of this type arise in many practical applications. It is known that the above joint generation problem can be solved in incremental quasi-polynomial time via a polynomial-time reduction to a generalization of the hypergraph transversal problem on integer boxes. In this paper we present an efficient implementation of this procedure, and present experimental results to evaluate our implementation for a number of interesting monotone properties π.     

Dynamics of composite functions meromorphic outside a small set

Let M denote the class of functions f meromorphic outside some compact totally disconnected set E=E(f) and the cluster set of f at any a∈E with respect to is equal to . It is known that class M is closed under composition. Let f and g be two functions in class M, we study relationship between dynamics of f○g and g○f. Denote by F(f) and J(f) the Fatou and Julia sets of f. Let U be a component of F(f○g) and V be a component of F(g○f) which contains g(U). We show that under certain conditions U is a wandering domain if and only if V is a wandering domain; if U is periodic, then so is V and moreover, V is of the same type according to the classification of periodic components as U unless U is a Siegel disk or Herman ring.