The complexity of monotone boolean functions

We study the realization of monotone Boolean functions by networks. Our main result is a precise version of the following statement: the complexity of realizing a monotone Boolean function ofn arguments is less by the factor (2/n)^1/2, where is the circular ratio, than the complexity of realizing an arbitrary Boolean function ofn arguments. The proof combines known results concerning monotone Boolean functions with new methods relating the computing abilities of networks and machines.     

Random walks for selected boolean implication and equivalence problems

This paper is concerned with the design and analysis of a random walk algorithm for the 2CNF implication problem (2CNFI). In 2CNFI, we are given two 2CNF formulas f₁{\phi_{1}} and f₂{\phi_{2}} and the goal is to determine whether every assignment that satisfies f₁{\phi_{1}} , also satisfies f₂{\phi_{2}} . The implication problem is clearly coNP-complete for instances of kCNF, k ≥ 3; however, it can be solved in polynomial time, when k ≤ 2. The goal of this paper is to provide a Monte Carlo algorithm for 2CNFI with a bounded probability of error. The technique developed for 2CNFI is then extended to derive a randomized, polynomial time algorithm for the problem of checking whether a given 2CNF formula Nae-implies another 2CNF formula.     

A minimization method for boolean functions

Algorithms are proposed for constructing one and all prime implicants covering a given point, a DNF consisting of prime implicants, and a reduced DNF. The complexity of the proposed algorithms is investigated.Translted from Kibernetika, No. 5, pp. 44–48, September–October, 1989.     

布尔函数和伪布尔函数多项式表示的快速实现算法

布尔函数和伪布尔函数在不同的领域有着广泛的应用,利用多项式表示有利于刻划它们的一些特征属性。论文首先在已知输入都能得到输出的条件下给出了布尔函数多项式表示的快速实现算法,该算法仅用到模2加运算,运算次数少,具有简洁、易于编程实现、准确而快速的特点,而且该算法很易推广为伪布尔函数多项式表示的快速实现算法,只需把模2加运算换成实数加运算即可。接着通过比较说明了伪布尔函数多项式表示的快速实现算法,同时指出任何伪布尔函数都能通过多项式形式表示出来。最后通过实例进一步验证了算法的正确性。     

On boolean functions and connected sets

Theory of Computing Systems -     

Separable boolean functions and generalized Fibonacci sequences

It is well known that the Boolean functions can be represented by two-layer perceptrons, and a part of them, namely separable Boolean functions, can be represented by one-layer perceptrons. How many separable Boolean functions of n variables there are is an open problem. On the other hand, given a n-element set X, how many antichains does P(X) have is also an open problem. This paper established an inequality reflecting the relationship between these two open problems. Second, this paper introduced two classes of Boolean functions which are generalizations of AND-OR functions and OR-AND functions, respectively, and proved that they are all separable and the weights in representing them are exactly terms of corresponding generalized Fibonacci sequences.     

布尔函数的代数免疫性研究

代数免疫性是评判布尔函数安全性的一个重要指标,研究了布尔函数的零化函数的性质,得到了代数免疫度的一些结果,同时研究了代数免疫度与布尔函数的重量的关系。     

Monotone circuits for monotone weighted threshold functions

Weighted threshold functions with positive weights are a natural generalization of unweighted threshold functions. These functions are clearly monotone. However, the naive way of computing them is adding the weights of the satisfied variables and checking if the sum is greater than the threshold; this algorithm is inherently non-monotone since addition is a non-monotone function. In this work we by-pass this addition step and construct a polynomial size logarithmic depth unbounded fan-in monotone circuit for every weighted threshold function, i.e., we show that weighted threshold functions are in mAC¹. (To the best of our knowledge, prior to our work no polynomial monotone circuits were known for weighted threshold functions.)Our monotone circuits are applicable for the cryptographic tool of secret sharing schemes. Using general results for compiling monotone circuits (Yao, 1989) and monotone formulae (Benaloh and Leichter, 1990) into secret sharing schemes, we get secret sharing schemes for every weighted threshold access structure. Specifically, we get: (1) information-theoretic secret sharing schemes where the size of each share is quasi-polynomial in the number of users, and (2) computational secret sharing schemes where the size of each share is polynomial in the number of users.     

An explicit construction of short monotone formulae for the monotone symmetric functions

We construct formulae that assume the value 1 when and only when at least k of their n variables assume the value 1, using only conjunction and disconjunction, and having (for any fixed k) only

$\text{O}\text{(n}\text{log}\text{n)}\text{k}\text{2}{}^{\mathrm{<mtext>log</mtext><mtext>1n</mtext>}}$

occurences of variables.     

Optimal sequential arrangement of evaluation trees for boolean functions

Let F be a disjunction of boolean functions of pairwise disjoint variables. Suppose an evaluation tree is given for each such function. We consider the problem of finding an optimal sequential order of scanning the trees for evaluation of F. A necessary and sufficient condition is given.A more general arrangement—a tree—structured arrangement of the trees is considered. It is shown to give no improvement.     

Optimal bounds for the approximation of boolean functions and some applications

This paper presents an optimal bound on the Shannon function L(n,m,) that gives the worstcase circuit-size complexity to approximate, within an approximation degree at least , partial boolean functions having n inputs and domain size m. That is

Full-size image

. Our bound applies to any partial boolean function and any approximation degree, and thus completes the study of boolean function approximation introduced by Pippenger (1977).

Our results give an upper bound for the hardness function h(ƒ), introduced by Nisan and Wigderson (1994), which denotes the minimum value l for which there exists a circuit of size at most l that approximates a boolean function ƒ with degree at least 1/l. Indeed, if H(n) denotes the maximum hardness value achieved by boolean functions with n inputs, we prove that for almost every nH(n)n/3 + n² + O(1). The exponent n/3 in the above inequality implies that no family of boolean functions exists which has ‘full’ hardness. This fact establishes connections with Allender and Strauss' (1994) work that explores the structure of BPP.

Finally, we show that for almost every n and for almost every boolean function ƒ of n inputs we have h(ƒ)2^{n/3−2 log n}. The contribution in the proof of the upper bound for L(n, m, ) can be viewed as a set of technical results that globally show how boolean linear operators are ‘well’ distributed on the class of 4-regular domains. This property is then applied to approximate partial boolean functions on general domains using a suitable composition of boolean linear operators.     

Information theory and the complexity of boolean functions

This paper explores the connections between two areas pioneered by Shannon: the transmission of information with a fidelity criterion, and the realization of Boolean functions by networks and formulae. We study three phenomena:

Using Petri net graphs express boolean functions

Both the combination and sequential switching function, also called switching circuits, can be represented by the binary code with Boolean algebra and Finite State Machine （FSM）. The basic elements of Petri net graph, such as place nodes, transition nodes, arcs, and tokens are used to frame the OR, NOT, and NOR logic function. Furthermore, to illustrate AND, and NAND switching function using the foregoing switching function, which is implemented by the Petri net graph. The main purpose of the paper is to prove ours hypothesis that the most logic function can be represented by the Petri net graph. Ultimately, our assumptions are complemented trustily.     

A general purpose fuzzy controller for monotone functions

In this work, a general purpose fuzzy controller is proposed to handle the class of monotonic functions. A set of rules on the selection of fuzzy subsets and decision tables based on the mean-of-inversion (MOI) defuzzification method for guaranteed convergence and accuracy is given and proved. Unlike the mean-of-maximum (MOM) and the center-of-area (COA) methods, the MOI method defuzzifies each fired rule separately instead of superimposing fired rules before defuzzification