在计算机理论研究中，最广为人知的问题莫过于 P 和 NP 的相等与否问题。这个问题从计算复杂度被定义的那一刻开始，就伴随着所有理论计算机的研究工作。如今，这个问题已经成为计算机理论研究中最重要的问题，也被归类为百万美元奖金问题中的头号难题。至今为止，计算机理论科学家们都并没有能够证明 P 和 NP 之间的关系。
要想了解 P = NP 问题，首先我们要知道什么是 P，什么是 NP。我们知道，每一个问题都分为可解（decidable）和不可解（undecidable）的，所谓可解，就是这个问题至少有一个算法能够让一台计算机运行后得出正确结果，而所谓不可解，就是永远不可能存在一个算法来在任何一台计算机上计算它并且得出正确结论。而针对所有可解的问题，它可能拥有不止一个算法，而这些算法中，就会有复杂度之分。简而言之，有些算法运行的快，有些算法运行的慢，而这就是所谓的算法复杂度。
P 和 NP
如果有一个问题，存在一个算法能够在多项式时间内结束运行并且得出正确结论，那么我们将这个问题归类为 P 问题，同时，我们也认为这类问题是容易的。反之，如果有一个问题，存在一个对应的算法能够在指数时间内解出这个问题并得出正确结论，那么我们将其成为 NP 问题。很明显，所有 P 问题都属于 NP 问题，因为多项式时间永远短于指数时间，但是，是否所有的 NP 问题都属于 P 问题，这就是著名的 P = NP 问题。
证明手段
为了证明 P 和 NP 的相等性或不等性，我们引入另一个问题归类，也就是 NP 完全问题。如果有一个问题，我们针对其写出一个算法，而这个算法可以用来计算所有 NP 问题，那么这个问题就被称为 NP 完全问题，同时我们也称这个问题是困难的。简而言之，只要我们能够解决一个 NP 完全问题，那么我们可以解决所有 NP 问题。因此，假如我们能够证明任何一个 NP 完全问题其实也是一个 P 问题，那么我们就证得了 P = NP，反之，假如我们能够证明任何一个 NP 完全问题不可能拥有一个多项式时间内运行的算法，那么我们就证明了 P 和 NP 的不等性。
P = NP 的逻辑性冲突
在多年的研究中，绝大多数理论学家们相信，P 和 NP 是不想等的，因为如果它们相等，会造成一连串不可预测的结果。
我们知道，P 问题又被称为简单问题，NP 完全问题又被成为困难问题，假如 P = NP，也就是说所有的困难问题都能被简单的解决，甚至是说，世界上所有的问题都能够被简单的解决。我们在逻辑层面上相信，抄写一本数学书和撰写一本数学书是不同的，而撰写一本数学书哦要比抄写一本数学书难得多。然而，假如 P 和 NP 相等，撰写一本数学书和抄写一本数学书是同样难的。然而，除了我们的逻辑，我们没有任何证据能够证明 P 和 NP 的不相等性。
同时，相当多的计算机应用也是建立在 P 和 NP 的不相等上的。最值得提到的就是密码学的应用。可以说，现今所有的密码，在一定层面上都是“可破解的”。假设破解一个密码需要一个算法运行最少七天，而我们能做的就是在七天之内修改密码。然而，如果 P = NP，那么所有破解过程都是“容易的”，因而，整个密码学的根基都会动摇。
最后，我们相信，如果 P =？NP 问题得证，其证明应当是相当简洁明了的，如同图灵的 Halting Problem 证明一般巧妙。
关注微信