为什么在NP中没有这个不确定的问题？

Question

显然，NP中没有任何不可决定的问题。但是，根据 维基百科:

NP是所有决策问题的集合，该问题的答案为“是”的实例具有确定性图灵机在多项式时间内可验证的[..证明]。

[...]

当且仅当存在一个在多项式时间内执行的问题的验证者时，就会说问题在NP中。

现在考虑以下问题：

给定 双方方程, ，它有任何整数解决方案吗？

给定解决方案，很容易在多项式时间内验证它的确 是 解决方案：只需将数字插入方程式即可。因此，问题在NP中。然而， 解决 这个问题是著名的 已知不确定!

（同样，似乎停止问题应该在NP中，因为可以通过n个步骤验证“该程序停止在n-the步骤”的“是” - 解决方案。）

显然，我的理解有什么问题，但是这是什么？

Answer 1

NP的等效定义是它由所有问题组成 可决定 （不仅仅是可验证的）在多项式时间内通过非确定性的图灵机。众所周知，NTM的功能比TMS更强大，因为NTM可决定的一组问题与TMS可确定的一组问题相同，因此，从这个定义中，NP中没有无法确定的问题。

为了证明NP的两个定义是等效的，鉴于确定性验证者的存在，您可以证明存在非确定性决定者，反之亦然。

假设您有一个确定性的多项式验证器。然后，还有一台机器，该机器非确定地猜测与该问题/验证者的证书大小相对应的多项式界限的长度证书，然后运行验证者。由于字母表是有限的，因此任何给定输入的证书都是有限的（最多在输入大小的多项式），并且验证者在多项式时间内运行，机器在所有分支上停止所有输入，并运行（非 - 确定性）多项式时间。因此，每个确定性验证者都有一个非确定性决定者。

如果您有一个不确定性的决定者，那么对于每个接受计算，您都可以写下决定者所采取的选择以达到接受状态的选择。由于决定者在多项式时间内运行，因此该路径最多为多项式长度。确定性的TM很容易验证这样的路径 是 通过NTM到达的有效路径，因此，此类路径为问题的多项式时间验证器形成证书。因此，每个非确定性决定者都有一个确定性的验证器。

因此任何不可确定的问题 不能 具有一个可用于多项式大小证书的验证者（否则验证者的存在将暗示决定者的存在）。

---

当您声称存在停止问题的验证者时，您要谈论的证书是（TM，i，n）的一些编码，其中TM在n步骤中停止输入I。确实可以通过n个步骤进行验证，但是证书的大小不是在原始问题（停止问题）的（TM，i）输入的（TM，i）输入的大小中； n可以任意大（无论编码如何）。如果您尝试将这种验证符转换为非确定性决定者，则最终会得到一台有趣的机器。您应该能够证明当（tm，i）进行tm时，您应该能够证明 不 在输入上停止了我没有通过机器的未挂钩路径，但对于任何导致停止状态的路径也总是有另一个更长的路径（对应于较大n的猜测），因此没有有限的有限键其执行时间。从本质上讲，这是因为有一个无限的空间需要通过最初的非确定性猜测来探索。将这样的NTM转换为 确定性 TM会导致其中一台既不循环也不停止某些输入的机器。实际上，没有任何可以决定停止问题的NTM，因此没有验证器可用于有界尺寸的证书。

我对Diophantine方程不太熟悉，但是看起来与您的论点相同。

因此，我发现对NP的NTM定义进行推理更容易。有一些不可决定的问题的验证符（只是在具有多项式大小的证书大小与原始问题的大小结合的证书中起作用的问题）。实际上任何TM 认识 但没有 决定 某些语言可以轻松地转换为相同语言的验证者。

如果您确实考虑了验证符，我想您必须就其时间界限 原始问题 输入，而不是证书大小；您可以任意夸大证书的大小，以便验证者在较低的时间内以证书的规模运行。

Answer 2

我认为您误解了解决二磷剂方程的含义，并且 Matiyasevich的不可可取性定理.

Matiyasevich证明，对于每个RE SET $ S $，都有一个diophentine方程$ f（n; x_1，...，...，x_k）$，因此仅在存在整数系数$ x_1 $，..，..，..，..，..， $ x_k $使$ f（n; x_1，...，x_k）= 0 $。特别是，停止问题是一个典型的RE集，因此解决上述问题是不可决定的。

请注意，$ x_1，... x_k $的大小没有界限，通常可以任意大，因此此问题中没有“多项式大小证书”。

要展开：整数$ x_1，...，x_k $需要用二进制编写为证书。由于这些整数可以任意大（无论$ n $如何），因此我们认为证书不是$ log n $或更重要的，不受可计算函数的限制。

但是，$ mathsf {np} $中的每个问题都有一个由某些多项式$ p（n）$（其中$ n $的输入大小）界的证书。因此，$ mathsf {np} $问题是可行的，因为您可以枚举所有可能的位字符串到长度$ p（n）$，并且如果没有一个人证明输入，请返回false。如果有些确实返回true。

Answer 3

您应该向下滚动到 正式定义:

且仅当存在多项式$ P $和$ Q $以及确定性的Turing Machine $ M $时，语言$ L $在NP中是NP

• 对于所有$ x $和y，计算机$ m $在输入$（x，y）$上运行$ p（| x |）$。
• 对于所有$ x in l $，存在一个长度$ q（| x |）$的字符串$ y $，使得$ m（x，y）= 1 $。
• 对于所有$ x not in L $和所有字符串$ y $ a length $ q（| x |）$，$ m（x，y）= 0 $。

也就是说，验证者也必须在非分解方面工作。在其中的某个地方，不确定的问题失败了（就您而言，解决方案候选者的长度限制可能无法满足），这显然（从可计算性意义上讲）更清晰 定义:

NP是在多项式时间内运行的非确定性图灵机可决定的一组决策问题。

Answer 4

我尝试为上述答案提供更多详细信息。

实际上，这个问题是一个困境问题。

一方面，根据Matiyesevich的定理（Matiyesevich的定理回答了希尔伯特的第十个问题，而图灵的停止问题回答了希尔伯特的第十个问题的概括，也就是说，ientscheidungsprobrem extraft of the enentscheidungsproblemboy）；但另一方面，根据NP的定义（可确定和可验证），NP中没有任何无法确定的问题。

也就是说，要么DEP不在NP中，要么DEP在NP中。他们俩都涉及NP的定义。

如果DEP不在NP中，则意味着NP中的问题（NDTM ＝无确定的Turing Machine）是可决定的，也可以证实，也就是说，我们接受P = NP（NDTM）。

如果DEP在NP中，则NP（NTM ＝非图灵机）包含可决定的和不可决定的，显然是可验证的，因此问题是不可证实的吗？实际上，这是Ps. NP的著名问题。当然，不可证明是无法验证的，因此NP对应于NTM（非图灵机），而不是NDTM（非确定图灵机）。

在DEP的前提下是在NP（NTM）中，我们认为NP（NTM）是无确定性的问题（不确定的），并且当前的NP（NDTM，可确定和可验证）的定义失去了这种非确定性（无法确定的），因此我们认为它需要受到质疑。

Answer 5

我们认为，您对二苯胺方程式提出的困境非常重要，因为它在当前的NP定义中揭示了异常的问题： - 当且仅当存在一个在多项式中执行的问题的验证者时，就会说一个问题是在NP中。时间。

关于NP的定义，可以追溯到60年代，在这里发现了许多适用和重大问题，没有发现多项式算法可以解决它们，以便从可在多项式时间中解决的这些问题中识别出这些问题（p），提出了NP的概念。

但是，在多项式时间内定义为可验证的NP的当前定义将NP与P混淆，因为P中的问题在多项式时间内也可以验证。在另一个单词中，这种定义导致NP的本质丧失，“非确定性”。因此，它导致理解NP的严重歧义，例如，您的困境：从本质上讲，二磷剂方程的问题是不可决定的。但是根据NP的定义，它是可决定的，…

我们认为，解决«P与NP»的困难首先是在认知水平上，因此，如果我们希望深入了解«P与NP'，我们首先需要提问：什么是NP？