这是我的第一个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的二进制表示？