它是针对特定 NP 完全问题的多项式时间算法，还是只是证明存在 NP 完全问题解决方案的抽象推理？
似乎特定的算法更有帮助。有了它，我们要多项式解决一个 NP 问题，我们要做的就是将其转换为证明有解决方案的特定 NP 完全问题，我们就完成了。
问问题
5559 次
15 回答
17
叫我悲观，但它会是这样的：
...
∴, P ≠ NP
量子点
于 2009-05-22T22:49:21.887 回答
15
有一些关于 P=NP 或 P≠NP 证明看起来不像的元结果。细节是相当技术性的，但众所周知证明不能
relativizing，这意味着证明必须使用所使用的图灵机的确切定义，因为进行了一些修改（“oracles”，例如添加到指令集中的非常强大的 CISC 指令）P = NP，并进行了一些其他修改, P≠NP。另请参阅此博客文章，了解相对化的一个很好的解释。
或algebrizing，相对化的概括。
于 2009-05-23T04:13:47.220 回答
5
它可以采取证明假设 P ≠ NP 会导致矛盾的形式。
于 2009-05-22T23:00:22.143 回答
4
它可能不会以直接的方式连接到 P 和 NP……现在许多定理都基于 P!=NP，因此证明一个假设的事实是不正确的会产生很大的不同。即使证明 TS 的恒定比率近似之类的东西也应该足够 IIRC。我认为，NPI（GI）和其他集合的存在也是基于 P！= NP，因此使它们中的任何一个等于 P 或 NP 可能会彻底改变这种情况。
恕我直言，现在一切都发生在一个非常抽象的层面上。如果有人证明了关于 P=/!=NP 的任何事情，则不必提及这些集合中的任何一个，甚至不必提及特定问题。
于 2009-05-22T23:03:24.057 回答
3
设置 N 等于乘法恒等式。那么 NP = P. QED。;-)
于 2009-05-22T23:18:03.043 回答
3
最直接的方法是证明 NP-complete 类中的问题存在多项式时间解。这些是 NP 中的问题，可以简化为已知的 np 问题之一。这意味着您可以提供更快的算法来证明斯蒂芬库克或许多其他人提出的原始问题，这些问题也被证明是 NP 完全的。请参阅 Richard Karp 的开创性论文和这本书更多有趣的问题。已经表明，如果你解决了其中一个问题，整个复杂性类别就会崩溃。编辑：我必须补充一点，我正在和正在研究量子计算的朋友交谈。虽然我不知道这意味着什么，但他说某个证明/实验？在量子世界中可以使整个复杂性类别，我的意思是整个事情，没有实际意义。如果这里有人对此有更多了解，请回复。
在没有给出正式算法的情况下，对该问题也进行了多次尝试。你可以试着数一数。有罗伯特/西摩证明。人们还尝试使用久经考验的对角化证明来解决它（也用于表明存在您永远无法解决的问题）。Razborov 还表明，如果存在某些单向函数，那么任何证据都无法给出解决方案。这意味着需要新技术来解决这个问题。
原论文发表至今已 38 年，至今仍无证据。不仅如此，数学家在复杂性类的概念出现之前提出的许多问题都被证明是 NP。因此，许多数学家和计算机科学家认为，其中一些问题是如此根本，以至于可能需要一种新的数学来解决这个问题。你必须记住，人类所能提供的最优秀的人才已经解决了这个问题，但没有任何成功。我认为至少需要几十年才能有人破解这个谜题。但即使存在多项式时间解，常数或指数也可能非常大，以至于在我们的问题中毫无用处。
有一个很好的调查可以回答你的大部分问题：http ://www.scottaaronson.com/papers/pnp.pdf 。
于 2009-05-23T16:13:14.403 回答
2
当然，描述性证明是最有用的，但还有其他类型的证明：例如，可以提供“存在性证明”来证明可以在不找到答案的情况下找到答案（或者，有时甚至建议如何找到）那个答案。
于 2009-05-22T22:36:10.930 回答
2
它可能看起来几乎完全像其中之一
于 2009-06-02T02:57:09.100 回答
1
好问题; 它可以采取任何一种形式。显然，特定的算法会更有帮助，是的，但是没有确定这将是理论 P=NP 证明发生的方式。鉴于 NP 完全问题的性质以及它们的普遍性，似乎在解决这些问题上付出的努力比在解决等式的理论推理方面付出的努力更多，但这只是假设。
于 2009-05-22T22:37:31.207 回答
1
任何 P=NP 确实不是的非建设性证明。这意味着以下显式 3-SAT 算法在多项式时间内运行：
枚举所有程序。在第i轮，运行所有编号小于i的程序一步。如果程序以对公式的满意输入而终止 ，则返回true。如果程序以不存在此类输入的正式证明终止，则返回 false。
如果 P=NP，那么存在一个运行在 O(poly(N)) 中的程序，如果存在这样的公式，则向公式输出一个令人满意的输入。
如果 P=coNP，则存在一个在 O(poly(N)) 中运行的程序，如果不存在公式，则输出不存在公式的正式证明。
如果 P=NP，那么由于 P 在补码 NP=coNP 下是封闭的。因此，存在一个在 O(poly(N)) 中运行并且两者都运行的程序。该程序是枚举中的第k个程序。k 是 O(1)！由于它在 O(poly(N)) 中运行，我们的蛮力模拟只需要
k*O(聚(N))+O(聚(N))^2
一旦它到达有问题的程序，就会进行轮次。因此，蛮力模拟在多项式时间内运行！
（请注意，k 是程序大小的指数；这种方法实际上并不可行，但它表明很难做出 P=NP 的非建设性证明，即使是这种情况。）
于 2009-05-27T00:52:52.660 回答
0
在某种程度上，这种证明需要具有的形式取决于您的哲学观点（=您认为正确的公理） - 例如，作为一个建构主义者，您会要求构建一个需要多项式时间来解决的实际算法一个NP完全问题。这可以通过使用归约来完成，但不能使用间接证明。无论如何，这似乎真的不太可能:)
于 2009-05-23T05:01:06.997 回答
0
该证明将推断出与 NP 的至少一个元素（问题）不是 P 的元素的假设相矛盾。
于 2009-05-24T00:25:25.253 回答
0
于 2009-09-03T10:00:44.320 回答