aeg*_*nia 8 complexity-theory np
这是我的第一个stackoverflow问题,所以要温柔.如果已经被打死了,我会事先道歉......我在NP上读了一些帖子,但我没有找到一个诱人的答案我的问题(如果有的话,我想出了一些新的).简述:
我怀疑第一个问题的答案是响亮的"是",而第二个问题的答案是响亮的"不".
在第一种情况下,示例问题可能是"给定集合S,S的子集T和具有域2 ^ S的函数f,确定T是否最大化f".对于通用的S,T和f,如果不检查S的所有子集X的f(X),你甚至无法验证这一点,对吗？
在第二种情况下......好吧,我承认这更像是一种预感.出于某种原因,似乎答案是否应该包含一位(用于决策问题)或任何(有限)位数......或换句话说,为什么你不应该考虑作为"答案"的一部分,TM停止后留在磁带上的符号.
编辑:实际上,我有一个问题......你的结构如何表明功能问题"比决策问题更难"？如果有的话,你已经表明,回答功能问题并不比决策问题更容易......这是微不足道的.也许这是以粗心的方式提出问题的错.
给定NP中的TM T1解决了变量X的"X是问题P的解决方案"和(为了参数)固定P的问题,是否保证在NP中将存在TM T2,其中T1停止到处停止,它在停止的任何地方以"停止接受"状态结束,并在磁带上留下例如X的二进制表示？
Gar*_*ees 15
(1)是的,决策问题是可以判定的但不是NP.NP⊊NEXP 是时间层次定理的结果,因此任何NEXP难问题都不在NP中.典型的例子就是这个问题:
给定一个非确定性的图灵机M和一个用二进制写的整数n,M 在最多n步中接受空字符串吗？
这个问题当然是可判定的(只是模拟长度为n的M的所有计算路径,如果看到任何接受).
有关更多NEXP完整问题,请在cstheory.stackexchange.com上查看此问题.当然,在NEXP之外存在决策问题:实际上,它们的整个指数层次结构 ......
(2)你的第二个问题的答案是否定的:功能问题并不比决策问题困难.(在"比没有更努力."一个特定的技术意义上的)假设我们有一个函数问题,询问输出ñ.然后是一个决策问题,它接受输入k并询问N的第k位是否为1.解决了答案中每一位的这个决策问题,你就完成了!
例如,FSAT(找到布尔公式的令人满意的赋值的问题)可以是多项式时间减少到SAT(确定布尔公式是否具有令人满意的赋值的问题).假设您可以解决SAT问题,并且要求您为公式φ找到令人满意的分配.首先考虑的变量X在公式φ,并询问是否SAT X ∧φ是满足的.如果是,则必须有一个令人满意的分配,其中x为真; 如果不是,并且φ是可满足的,那么对于其中x为假的φ必须有令人满意的分配.与第二可变继续Ÿ,询问是否X ∧ Ÿ ∧φ(或¬ X ∧ Ÿ ∧φ,根据回答你的第一个问题)是满足的.等等公式中的每个变量.
[我应该对这个例子添加一个重要的警告.在这里,SAT和FSAT是"自然"相关的:他们都关注同一类事物,即满足公式的赋值.但是在我的观点中,搜索通常可以简化为决策,我使用了关于输出的第k位的高度人为的决策问题.因此,虽然搜索减少到决策,但它不一定会减少到自然对应的决策问题.特别是,Bellare和Goldwasser表明有时搜索不能减少.]