Random Structures and Algorithms · 1997 · 46 citations · 0 references
ComputingComputer ScienceMathematicsCombinatoricsProbability TheoryTheory Of ComputationCircuit ComplexityComputational ComplexityProbabilistic CombinatoricsStructural ComplexityBinary TreesBoolean Circuit ComplexityBoolean EquationsBoolean Formula SizeBoolean Function ComplexityCircuit Size ComplexityComplexity Of Boolean FunctionsFormula Complexity
In this paper typical properties of large random Boolean AND/OR formulas are investigated. Such formulas with n variables are viewed as rooted binary trees chosen from the uniform distribution of all rooted binary trees on m nodes, where n is fixed and m tends to infinity. The leaves are labeled by literals and the inner nodes by the connectives AND/OR, both uniformly at random. In extending the investigation to infinite trees, we obtain a close relation between the formula size complexity of any given Boolean function f and the probability of its occurrence under this distribution, i.e., the negative logarithm of this probability differs from the formula size complexity of f only by a polynomial factor. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 10, 337–351 (1997)