PNP问题(P versus NP problem)是哪个由著名逻辑学家、哈佛大学计算机科学家Stephen Cook在1971年首次提出。直到现在，这个问题仍是未解决的世界级经典问题，挑战无数的数学家、计算机科学家等专业人士。
PNP问题的核心在于，探究一个问题能否通过多项式时间解决（P——多项式时间类）和那个问题的解能否在多项式时间内被检验（NP——非确定性多项式时间类）之间的关系。这里的”多项式时间”是指解决问题的时间和问题规模之间呈多项式关系，也就是说，随着问题规模的增大，解决问题所花费的时间呈多项式增长。
1971年，Stephen Cook在其论文”The Complexity of Theorem Proving Procedures”中，首次对P与NP问题进行了正式的描述。他提出了我们今天所知的P=NP问题，并用所谓的”NP-complete” (NP完全问题)来描述那些最困难的NP问题。如果对这些NP完全问题可以找到多项式时间的解决方案，那么我们可以说P=NP。在此之后，理查德·卡普(Richard Karp)进一步确定了21个特定的NP完全问题，诸如：图着色问题、旅行商问题等。
然而P=NP仍然是一个未解决的问题，也就是我们并不清楚p和np是否等价。直到现在，人们会对其的答案会引出两种相反的推测，一部分人认为P≠NP，另一部分人认为P=NP。这其中的奥秘在于，虽然目前我们还没找到证明P≠NP的方法，同时也没有找到证明P=NP的方法。研究这个问题，不仅对理论计算机科学有重大意义，同时也对许多实质性的问题如密码学、操作研究等有重大影响。
虽然至今PNP问题尚未解决，但对它的研究已经产生了深远影响，推动了计算机科学、运筹学、数学等多个领域的发展。同时，它的存在也挑战了我们的思维，推动了我们探寻那些关乎虚实、可能与否的问题，使我们更深入地理解了问题解决的本质。
声明：本站仅提供存储服务。部分图文来源于网络，版权归原作者所有，不代表本立场或观点。如有侵权，请联系删除。
作者：8665636@qq.com，本文链接：https://www.vibaike.net/article/2013840.html
