10

这是我的第一个 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 的问题“X 是问题 P 的解决方案”并且（为了论证）固定 P，是否保证 NP 中会有一个 TM T2 在 T1 停止的任何地方停止，它在任何地方都以“停止接受”状态结束，并在磁带上留下例如 X 的二进制表示？

4

1 回答 1

16

(1) 是的，存在可判定但在 NP 中不可判定的判定问题。NP ⊊ NEXP是时间层次定理的结果，因此任何 NEXP-hard 问题都不属于 NP。典型的例子是这个问题：

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

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

有关更多 NEXP 完整问题，请参阅cstheory.stackexchange.com 上的此问题。当然，在 NEXP 之外还有决策问题：事实上，它们的整个指数层次结构......

（2）第二个问题的答案是否定的：功能问题并不比决策问题难。（在“不比”的特定技术意义上。）假设我们有一个要求输出N的函数问题。然后是一个决策问题，它接受一个输入k并询问N的第k位是否为 1。对答案中的每一位解决这个决策问题，你就完成了！

例如，FSAT（找到对布尔公式的满意分配的问题）可以多项式时间简化为 SAT（确定布尔公式是否具有令人满意的分配的问题）。假设您可以解决 SAT，并且要求您为公式 φ 找到一个令人满意的作业。考虑公式 φ 中的第一个变量x，并询问 SAT x ∧φ 是否可满足。如果是，则必须有一个令人满意的分配，其中x为真；如果不是，并且 φ 是可满足的，那么对于 φ 必须有一个令人满意的赋值，其中x为假。继续第二个变量y，询问是否x∧<i>y∧φ（或 ¬ x ∧<i>y∧φ，根据第一个问题的答案）是可以满足的。对于公式中的每个变量，依此类推。

[我应该对这个例子添加一个重要的警告。这里 SAT 和 FSAT 是“自然”相关的：它们都关注同一种事物，即满足对公式的分配。但是在我的论点中，搜索通常可以简化为决策，我使用了一个关于输出的第k位的高度人工决策问题。所以虽然搜索归结为决策，但不一定归结为自然对应的决策问题。特别是，Bellare 和 Goldwasser 表明，有时搜索不能如此减少。]

于 2011-07-15T20:32:41.300 回答