The hardness of the Expected Decision Depth problem

详细信息	查看全文 | 推荐本文 |

• 作者：Dana Ron ; Amir Rosenfeld ; Salil Vadhan
• 关键词：Computational complexity ; Decision trees
• 刊名：Information Processing Letters
• 出版年：2007
• 期刊代码：61_00200190
• 类别：cp
• 出版时间：14 February 2007
• 卷：101
• 期：3
• 页码：112-118
• 文件大小：162 K

摘要

Given a function f over n binary variables, and an ordering of the n variables, we consider the Expected Decision Depth problem. Namely, what is the expected number of bits that need to be observed until the value of the function is determined, when bits of the input are observed according to the given order. Our main finding is that this problem is (essentially) #P-complete. Moreover, the hardness holds even when the function f is represented as a decision tree.