algorithm - 假设 P=NP 证明是什么样的？

Question

它是针对特定 NP 完全问题的多项式时间算法，还是只是证明存在 NP 完全问题解决方案的抽象推理？

似乎特定的算法更有帮助。有了它，我们要做的就是用多项式求解 NP 问题，将其转换为证明有解的特定 NP 完全问题，然后我们就完成了。

Answer 1

P = NP:“3SAT 问题是一个经典的 NP 完全问题。在这个证明中，我们演示了一个求解它的算法，该算法具有 (n^99 log log n) 的渐近边界。首先我们 .. ”

P != NP:“假设有一个针对 3SAT 问题的多项式算法。这意味着......这意味着我们可以做......然后......然后……这是不可能的。这一切都基于 3SAT 的多项式时间算法。因此 P != NP。”

更新:可能类似于 this paper (对于 P != NP)。

更新 2:Here's a video of Michael Sipser sketching out a proof for P != NP