Some typical properties of large AND/OR Boolean formulas

✍ Scribed by Hanno Lefmann; Petr Savický

• Publisher: John Wiley and Sons
• Year: 1997
• Tongue: English
• Weight: 195 KB
• Volume: 10
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199705)10:3<337::aid-rsa4>3.0.co;2-x

✦ Synopsis

In this paper typical properties of large random Boolean ANDrOR 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 ANDrOR, 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.