这是我的第一个stackoverflow问题,请温柔点。如果这个问题已经被讨论过了,我提前道歉...我看了一些NP的帖子,但没有找到一个令人心动的答案(如果有什么的话,我想到了一些新问题)。简而言之:
- 是否存在可判定但不在NP中的决策问题?
- 如果是,那么要求解的问题是否比等效的决策问题更难?
我的猜测是,第一个问题的答案是肯定的,而第二个问题的答案是否定的。
对于第一个问题,一个示例问题可能是“给定集合S、S的子集T和定义域为2^S的函数f,确定T是否最大化了f”。对于通用的S、T和f,你甚至不能在检查S的所有子集X的f(X)之前验证这个问题,对吗?
对于第二个问题...好吧,我承认这更像是一种直觉。由于某种原因,似乎答案包含一个位(对于决策问题)或任意(有限)数量的位都无关紧要...换句话说,为什么你不能将TM停止后留在磁带上的符号视为“答案”的一部分。
编辑: 实际上,我有一个问题...你的构造如何精确地表明函数问题“不比”决策问题更难?如果说什么,你已经表明回答一个函数问题并不比回答一个决策问题更容易...这是显然的。也许这是我提出问题方式不够严谨的原因。
给定一个在NP中的TM T1,它解决了变量X和(为了论证)固定P的问题“X是否是问题P的解”,那么是否保证存在一个在NP中的TM T2,在T1停止的每个位置都停止,在它停止的每个位置结束于“停止接受”状态,并在磁带上留下X的二进制表示等信息?