The Computational Complexity of Game Trees by Eigen-Distribution
The Computational Complexity of Game Trees by Eigen-Distribution
复制标题
DOI：
10.1007/978-3-540-73556-4_34
复制
发表时间：
2007-08
期刊：
影响因子：
--
通讯作者：
Chenguang Liu;Kazuyuki Tanaka
中科院分区：
文献类型：
--
作者：
Chenguang Liu;Kazuyuki Tanaka
AND-OR树是计算只读布尔函数的一个非常简单的模型。对于与或树，特征分布是随机分配到叶子上的特殊分布，从而实现与或树的分布复杂性。Yao的原则[8]表明，任何函数的随机复杂度等于同一函数的分布复杂度。在目前的工作中，我们提出了一种基于特征分布的技术来计算只读布尔函数的分布复杂性。然后，将该方法与姚氏原理相结合，给出了布尔函数随机复杂性的一些著名结果的统一证明方法。
The AND-OR tree is an extremely simple model to compute the read-once Boolean functions. For an AND-OR tree, the eigen-distribution is a special distribution on random assignments to the leaves, such that the distributional complexity of the AND-OR tree is achieved. Yao’s Principle[8] showed that the randomized complexity of any function is equal to the distributional complexity of the same function. In the present work, we propose an eigen-distribution-based technique to compute the distributional complexity of read-once Boolean functions. Then, combining this technique and Yao’s Principle, we provide a unifying proof way for some well-known results of the randomized complexity of Boolean functions.