有可判定的决策问题，但不属于NP吗？

Question

这是我的第一个stackoverflow问题，请温柔点。如果这个问题已经被讨论过了，我提前道歉...我看了一些NP的帖子，但没有找到一个令人心动的答案（如果有什么的话，我想到了一些新问题）。简而言之：

1. 是否存在可判定但不在NP中的决策问题？
2. 如果是，那么要求解的问题是否比等效的决策问题更难？

我的猜测是，第一个问题的答案是肯定的，而第二个问题的答案是否定的。

对于第一个问题，一个示例问题可能是“给定集合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的二进制表示等信息？

- aegrisomnia

---

可能更适合于cstheory.stackexchange.com。 - Wooble

好建议。我会看看情况如何，并根据结果重新发布。谢谢！ - aegrisomnia

这个问题不适合于CSTheory，因为它不是一个研究级别的问题（[请参见FAQ]（http://cstheory.stackexchange.com/faq））。如果迁移，它将被关闭。我相信我们可以在这里回答它。 - Gareth Rees

不确定为什么会有这么多关闭投票，这对于cstheory.stackexchange.com来说是一个非常基础的问题。 - BlueRaja - Danny Pflughoeft

Answer 1

(1) 是的，有一些可判定但不属于NP的决策问题。这是由时间层次定理引起的，NP ⊊ NEXP，因此任何NEXP难问题都不属于NP。典型的例子是这个问题：

给定一个非确定性图灵机 M 和一个用二进制表示的整数 n，是否在最多 n 步内 M 接受空字符串？

这个问题肯定是可判定的（只需模拟长度为 n 的 M 的所有计算路径，如果看到任何接受，则接受）。

请参见cstheory.stackexchange.com上的这个问题，了解更多NEXP完全问题。当然，还有NEXP之外的决策问题：实际上，有一个指数层次结构...

(2) 对于你的第二个问题，答案是否定的：函数问题并不比决策问题更困难。(在一个特定技术意义上是这样的) 假设我们有一个函数问题，要求输出N。那么就有一个决策问题，它接受一个输入k并询问N的第k位是否为1。解决每个位的这个决策问题，你就完成了！

例如，FSAT(查找布尔公式的满足分配问题)可以多项式时间约化成SAT(确定一个布尔公式是否有满足分配的问题)。假设你能够解决SAT，并被要求为公式φ找到一个满足分配。考虑公式φ中的第一个变量x，并询问SAT是否可满足x∧φ。如果是，则必须存在一个使得φ满足且x为真的满足分配；如果不是，而φ是可满足的，则必须存在一个使得φ满足且x为假的满足分配。继续进行第二个变量y，并询问x∧y∧φ (或者根据第一个问题的答案询问¬x∧y∧φ)是否可满足。对公式中的每个变量都是如此。

关于这个例子，我应该添加一个重要的警告。在这里，SAT和FSAT是"自然"相关的：它们都涉及到相同类型的事物，即满足公式的分配。但是，在我将搜索“一般”减少到决策的论证中，我使用了一个高度人工的有关输出第k位的决策问题。因此，尽管搜索可以减少到决策，但不一定可以减少到“自然”的相应决策问题。特别地，Bellare和Goldwasser表明，有时候搜索无法被如此减少。

• M. Bellare和S. Goldwasser（1994年）。 "决策与搜索的复杂性。" SIAM Journal on Computing。 23:1 pp. 97-119。

- Gareth Rees

---

很容易对问题之间的缩减感到困惑！仔细思考一下，你就会看出哪一端是哪一端。 - Gareth Rees

我不喜欢第二个问题的答案。例如旅行商问题，“最短路径长度中的位#i是否为1”？很明显没有证明可以在多项式时间内验证。然而，如果所有路径的总和为K，则最短路径显然具有长度<= K，因此我们可以使用二分查找来决定“是否存在长度<= K/2的路径”，然后是“是否存在长度<= 3/4 K”的路径或“... <= 1/4 K”等等；每个都有一个明显的证明（该长度的路径），可以在多项式时间内验证。 - gnasher729

@gnasher729 你正在比较不相等的问题。TSP函数问题“找到最优路径”（FTSP）比“自然相关”的决策问题“是否存在路径<= K”（FTSP是NP难问题，TSP是NP完全问题）更难。请注意，他的论点表明函数问题并不比决策问题更难，因为如果您可以解决“ TSP中的第i位”决策问题，您也可以解决TSP函数问题，这就是为什么第i位问题也是NP难问题的原因。 - Mario Carneiro

可以详细说明一下第一点吗？直觉上，我认为问题在于解决该问题所提出的NTM对其非确定性的“分支因子”具有恒定的上限，但它需要模拟的NTM可能会使其分支因子与其描述长度成线性增长。因此，在每个步骤之后，模拟器分支数乘以一个与模拟器输入成线性关系的因子。 - isarandi

但似乎这只会导致模拟器所需深度的线性增加。我的第二个想法是可能与存储有关。为了模拟所有不同的分支，头部需要跳来跳去吗？ - isarandi