A survey of Evasiveness: Lower Bounds on the Decision-Tree Complexity of Boolean Functions
A survey of Evasiveness: Lower Bounds on the Decision-Tree Complexity of Boolean Functions
复制标题
回避性调查：布尔函数决策树复杂性的下界
DOI：
--
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
C. Chronaki
中科院分区：
文献类型：
--
作者：
C. Chronaki
n个参数的布尔函数F的决策树复杂度是在每个输入上正确计算F的最小深度决策树的深度。一个n个参数的布尔函数F是cn-evasive的，如果它的决策树复杂度是cn，（c < 1）。F是完全回避的，（n-回避），如果它的所有参数都需要在最坏的情况下被探测。当我们限制所考虑的布尔函数的性质和形式时，可以得出关于其决策树复杂性的有趣结果。一个这样的限制是布尔函数，它表示图的邻接矩阵。Rivest和Vuillemin证明了Aanderaa-Rosenberg猜想，即n个节点图的所有图的性质都是Cn 2-evasive的.随后证明了素数幂节点上的所有非平凡单调图性质都是完全回避的。然而，证明所有单调图的性质是回避似乎是一个艰巨的任务。在本文中，我们调查的证明技术用于建立布尔函数的回避在各种条件下的对称性和单调性。此外，我们探讨了这些条件对布尔函数的形式和复杂性的影响，旨在了解使布尔函数完全回避的质量。
The decision tree complexity of a boolean function F of n arguments is the depth of a minimum-depth decision tree that computes F correctly on every input. A boolean function F of n arguments is cn-evasive if its decision tree complexity is cn, (c < 1). F is completely evasive, (n-evasive), if all of its arguments need to be probed in the worst case. When we restrict the properties and form of the boolean functions considered, interesting results on their decision tree complexity can be derived. One such restriction is boolean functions which represent the adjacency matrix of a graph. Rivest and Vuillemin proved the Aanderaa-Rosenberg conjecture which stated that every graph property on n node graphs is c n 2-evasive. Subsequently it was proved that all nontrivial monotone graph properties on a prime power number of nodes are completely evasive. However proving that all monotone graph properties are evasive seems a diicult task. In this paper we survey the proof techniques used to establish the evasiveness of boolean functions under various conditions of symmetry and monotonicity. Furthermore, we explore the impact of these conditions on the form and complexity of the boolean functions, aiming to understand the qualities that make a boolean function completely evasive.