P vs NP：如何证明它们不相等？
P vs NP: How to prove that they are not equal?
所以如果存在可以在多项式时间内解决它的图灵机，那么问题就是P（=多边形时间）。对于 NP（= 非确定性多时间）问题，存在一个见证，图灵机可以利用它在多项式时间内解决问题（或决定它是否属于语言的一部分）。
if P = NP 的问题仍未得到证实。
不知道你怎么证明P不等于NP。我的想法是，如果你在NP中发现一个问题，然后证明没有算法，可以在poly time（没有witness）的情况下解决这个问题，那么P not equal NP.
因此，例如，如果您查看哈密顿路径问题（在 NP 中）并证明它不能通过确定性 TM 在多时间内解决，那么 P not equal NP。
我的思维过程是正确的还是我遗漏了什么？
我们有 NP complete 问题，最著名的问题是 SAT，还有许多其他问题，例如哈密尔顿路径。如果其中一个问题在 P 中，则 NP=P。如果其中之一不在 P 中——即，不存在任何决定该语言的多时间 TM——那么 NP != P。所以是的，证明 P 等于或不等于 NP 等同于证明确实存在或者不存在解决其中一个完整问题的算法（例如您举的汉密尔顿路径）。
所以如果存在可以在多项式时间内解决它的图灵机，那么问题就是P（=多边形时间）。对于 NP（= 非确定性多时间）问题，存在一个见证，图灵机可以利用它在多项式时间内解决问题（或决定它是否属于语言的一部分）。
if P = NP 的问题仍未得到证实。
不知道你怎么证明P不等于NP。我的想法是，如果你在NP中发现一个问题，然后证明没有算法，可以在poly time（没有witness）的情况下解决这个问题，那么P not equal NP.
因此，例如，如果您查看哈密顿路径问题（在 NP 中）并证明它不能通过确定性 TM 在多时间内解决，那么 P not equal NP。
我的思维过程是正确的还是我遗漏了什么？
我们有 NP complete 问题，最著名的问题是 SAT，还有许多其他问题，例如哈密尔顿路径。如果其中一个问题在 P 中，则 NP=P。如果其中之一不在 P 中——即，不存在任何决定该语言的多时间 TM——那么 NP != P。所以是的，证明 P 等于或不等于 NP 等同于证明确实存在或者不存在解决其中一个完整问题的算法（例如您举的汉密尔顿路径）。