证明 P <= NP
大多数人都知道，P = NP 未经证实，而且似乎不太可能是真的。证明将证明 P <= NP 和 NP <= P。不过，只有其中一个是困难的。
P <= NP 几乎根据定义为真。事实上，这是我知道如何表述 P <= NP 的唯一方法。这只是直观的。你如何证明 P <= NP？
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
NP 中的每个问题都由非确定性图灵机 [在多项式时间内] 解决。 （根据定义*）
P 中的每个问题都由确定性图灵机 [在多项式时间内] 解决。 （根据定义）
每个确定性图灵机也是一个非确定性图灵机。 （显然）
因此 P 中的每个问题都由非确定性图灵机[在多项式时间内]解决。
因此，P 中的每个问题都是 NP 中的问题。因此 P ⊆ NP。
*让我们阅读关于 NP 的维基百科文章：
没有必要将多项式验证这些东西引入到如此简单的推理中。
Each problem in NP is solved by a nondeterministic Turing machine [in polynomial time]. (by definition*)
Each problem in P is solved by a deterministic Turing machine [in polynomial time]. (by definition)
Each deterministic Turing machine is a nondeterministic Turing machine as well. (obviously)
Hence each problem in P is solved by a nondeterministic Turing machine [in polynomial time].
Hence each problem in P is a problem in NP. Hence P ⊆ NP.
*Let's read Wikipedia article on NP:
There's no need to introduce this stuff about polynomial verification into such a simple reasoning.
我认为您基本上已经在评论中回答了自己的问题：满足
P定义的问题也满足NP的定义。引用维基百科：
它所指的证书是解的多项式时间验证；正如您所说，您可以在多项式时间内解决
P中的问题，因此您将获得一个已在多项式时间内验证的解决方案，因此在NP中。乔伊·亚当斯的回答是第二种解释，即（非）确定性图灵机的可解性。请参阅维基百科文章，了解
NP 定义的更多说明。我认为你在这里应该注意的是，证明非常简单这一事实并不意味着它不是一个证明。 “根据定义”是一个完全有效的逻辑步骤。
I think you've essentially answered your own question in the comments: a problem which satisfies the definition of
Palso satisfies the definition ofNP.To quote wikipedia:
The certificate it refers to is the polynomial-time verification of solution; as you say, you can solve a problem in
Pin polynomial time and you will therefore have a solution which has been verified in polynomial time and is therefore inNP.Joey Adams' answer is the second explanation, in terms of solvability by (non)deterministic Turing machines. See the wikipedia article for a bit more explanation of that definition of
NP.I think what you should note here is that the fact that the proof is trivially simple doesn't mean it's not a proof. "By definition" is a perfectly valid logical step.
一台非确定性计算机可以简单地不调用其非确定性并像确定性计算机一样运行，因此它可以在多项式时间内运行 P 问题。这是我能想到的最好的答案。
A nondeterministic computer can simply not invoke its nondeterminism and act like a deterministic one, thus it can run P problems in polynomial time. That's the best answer I can think of.
在多项式时间内解决 (NP) 问题的非确定性计算机也将在多项式时间内解决 P 问题。
如果我们考虑图灵机的想象方法，它可以在决策时采取多条路径来在多项式时间内解决 NP 问题，那么这种行为必须足以在 P 时间内解决 P 问题。确定性图灵机是简单（真实）非确定性机器的一种情况。
A non-deterministic computer that solves a (NP) problem in polynomial time would also solve a P problem in polynomial time.
If we consider the imaginary approach of a Turing Machine that can take several paths at a decision to solve the NP problem in polynomial time, this behaviour must be enough to solve the P problem in P Time. Deterministic Turing machines are a case of simple (real) non-deterministic machines.
NP 中的每个问题都由非确定性图灵机 [在多项式时间内] 解决。 （根据定义*）
P 中的每个问题都由确定性图灵机 [在多项式时间内] 解决。 （根据定义）
每个确定性图灵机也是一个非确定性图灵机。 （显然）
因此 P 中的每个问题都由非确定性图灵机[在多项式时间内]解决。
因此，P 中的每个问题都是 NP 中的问题。因此 P ⊆ NP。
Each problem in NP is solved by a nondeterministic Turing machine [in polynomial time]. (by definition*)
Each problem in P is solved by a deterministic Turing machine [in polynomial time]. (by definition)
Each deterministic Turing machine is a nondeterministic Turing machine as well. (obviously)
Hence each problem in P is solved by a nondeterministic Turing machine [in polynomial time].
Hence each problem in P is a problem in NP. Hence P ⊆ NP.
ℙ≠ℕℙ 已证明。 https://sourceforge.net/projects/cscall/文件/MisFiles/PNP-proof-en.txt/download
...[切]
证明2：设p=“给定一个数n，判断n是否为偶数”。如果
ℙ=ℕℙ，则 p∉ℕℙℂ 的所有现有证明都是假证明（因为
所有 ℕℙ 问题（包括 ℕℙℂ）都可以相互 Ptime 简化）。自从
证明 p∉ℕℙℂ 为真，ℙ≠ℕℙ 成立。
ℙ≠ℕℙ Proved. https://sourceforge.net/projects/cscall/files/MisFiles/PNP-proof-en.txt/download
...[cut]
Proof2: Let p="Given a number n, determine whether or not n is even". If
ℙ=ℕℙ, then all the existing proofs of p∉ℕℙℂ are false proofs (because
all ℕℙ problems including ℕℙℂ will be mutually Ptime reducible). Since
the proofs that p∉ℕℙℂ are true, ℙ≠ℕℙ is concluded.