P与NP是相同还是不同？发现有许多问题是NP完全的，就意味着数学家有许多种方法来试图证明P=NP。无论哪一个NP完全问题，只要找到一个能解决它的多项式时间过程，那么就立即得到P=NP。例如，一个解决推销员问题的多项式时间过程，就是关于P=NP的一个证明。
不过，要证明P与NP不同，你必须去找一个你能证明不存在多项式时间过程解法的NP问题。这个问题可以是一个已知的问题。例如，如果你能证明推销员问题肯定无法用多项式时间过程解决，那么你就证明了P与NP并不相同。
这并不像你想的那样简单。取某个能解决推销员问题的特殊过程并且证明它不是多项式时间过程，这是不够的。证明迄今研究出的所有过程没有一个是以多项式时间运行，也是不够的。确切地说，你必须证明不可能存在以多项式时间解决这个问题的过程。这意味着你的证明必须考虑可以解决这个问题的任何过程，不仅仅是那些已知的，还要包括将来可能发现的任何过程。
在圈外人看来这也许有些奇怪，但是数学家已在某些情况下能证明关于这种未知的对象集合的结果。库克对NP完全性的证明就是这样一种结果。他证明了如果他那个特殊的NP问题可以在多项式时间内解决，那么包括所有尚未发现的NP问题在内的任何其他NP问题都同样可以在多项式时间内解决。然而，在证明P≠NP的情况中，没人能证明存在某个NP问题，它无法用多项式时间过程求解。这就是P对NP问题为什么会成为一个千禧难题。
