Some typical properties of large AND/OR Boolean formulas
Some typical properties of large AND/OR Boolean formulas
复制标题
大型 AND/OR 布尔公式的一些典型属性
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
P. Savický
中科院分区：
文献类型：
--
作者：
H. Lefmann;P. Savický
本文研究了大型随机布尔与/或公式的典型性质。这些有n个变量的公式被看作是从所有有m个叶子的有根二叉树的均匀分布中选择的有根二叉树，其中n是固定的，m趋于无穷。叶子由字面量标记，内部节点由连接词and /OR标记，两者都是均匀随机的。将研究推广到无限树，得到了任意布尔函数f的公式大小复杂度与其在该分布下出现的概率之间的密切关系，即该概率的负对数与f的公式大小复杂度只相差一个多项式因子。
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 with m leaves, 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 an arbitrary 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.