Some typical properties of large AND/OR Boolean formulas
Hanno Lefmann, Petr Savick� · Random Structures and Algorithms · 1997
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)