P vs NP Problem

If it is easy to check that a solution to a problem is correct, is it also easy to solve the problem? This is the essence of the P vs NP question. Typical of the NP problems is that of the Hamiltonian Path Problem: given N cities to visit (by car), how can one do this without visiting a city twice? If you give me a solution, I can easily check that it is correct. But I cannot so easily (given the methods I know) find a solution.

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

Image credit: on the left, Stephen Cook by Jiří Janíček (cropped). CC BY-SA 3.0

1
Problem Statement. Does Ｐ = ＮＰ?

Ｐ = {L | L = L(M) for some Turing machine M that runs in polynomial time}.

The notation ＮＰ stands for “Nondeterministic Polynomial time”, since originally ＮＰ was defined in terms of nondeterministic machines (that is, machines that have more than one possible move from a given configuration).

To put it more briefly, Ｐ is the set of easy decision problems. ＮＰ is the class of decision problems for which it is easy to check the correctness of a claimed answer, with the aid of a little extra information. So we aren’t asking for a way to find a solution, but only to verify that an alleged solution really is correct.

In Ｐ are the problems where it’s easy to find a solution, and in ＮＰ are the problems where it’s easy to check a solution that may have been very tedious to find.

\(\huge \mathbf{P} \subset \mathbf{NP} \tt{?}\)

The crucial question related to Ｐ and ＮＰ is whether the subset relation is proper?

1
P ⊂ NP?

很显然的是Ｐ类都属于ＮＰ类（P ⊆ NP），这样问题就变成：是否某些NP类问题（比如旅行推销员问题）不存在多项式时间过程算法? 问题难在如何证明这一点？如何从逻辑上排除旅行推销员问题存在多项式时间过程算法的可能性？这跟黎曼假设的严格数学证明要排除临界线外有复零点的可能性一样困难。

复杂性范畴之间的包含关系：

\(\mathrm{LOGSPACE} \subseteq \mathbf{P} \subseteq \mathbf{NP} \subseteq \mathrm{PSPACE} \)
\(\mathrm{LOGSPACE} \subset \mathrm{PSPACE} \)

LOGSPACE ⊆ P ⊆ NP ⊆ PSPACE，用简单的对角化论证法能够证明 LOGSPACE 是 PSPACE 的真子集，其余的包含关系是否为真包含关系？无人能够证明。

很多研究复杂性理论的专家都认为 Ｐ≠ＮＰ，Scott Aaronson 从哲学角度发表了他的看法：“如果P = NP，那么我们就会处于一个截然不同的世界中，创造性飞跃将失去其难能可贵的价值，解决一个问题和认识到问题有解没什么分别。任何一个能欣赏交响乐的人都能成为莫扎特，任何一个懂得数学证明的人都能成为高斯…”。（If P = NP, then the world would be a profoundly different place than we usually assume it to be. There would be no special value in “creative leaps,” no fundamental gap between solving a problem and recognizing the solution once it’s found. Everyone who could appreciate a symphony would be Mozart; everyone who could follow a step-by-step argument would be Gauss…）。按 Stephen Cook 在白皮书中的说法，如果P = NP，那么机器就能给出克雷数学研究所七大难题的形式化证明，尽管证明会很繁琐很冗长。( If P = NP, …. For example, it would transform mathematics by allowing a computer to find a formal proof of any theorem that has a proof of reasonable length, since formal proofs can easily be recognized in polynomial time. Such theorems may well include all of the CMI prize problems. Although the formal proofs may not be initially intelligible to humans, the problem of finding intelligible proofs would be reduced to that of finding a recognition algorithm for intelligible proofs. Similar remarks apply to diverse creative human endeavors, such as designing airplane wings, creating physical theories, or even composing music. The question in each case is to what extent an efficient algorithm for recognizing a good result can be found. This is a fundamental problem in artificial intelligence, and one whose solution itself would be aided by the NP-solver by allowing easy testing of recognition theories. )

在克雷数学研究所的官方资料中，此问题由 Stephen Cook （创造性地提出 ＮＰ-complete 概念并证明The satisfiability problem是NP-完全问题）作出权威解读。

相关的经典论文

  • Finite Automata and Their Decision Problems, Michael O. Rabin & Dana Scott, 1959
  • The Complexity of Theorem-Proving Procedures, Stephen A. Cook, 1971
  • Reducibility among combinatorial problems, Richard Karp, 1972

数学元素

  • 图灵机（Turing Machine）
  • 可计算性
  • NP-完全：如果图论中的哈密顿回路有类似欧拉回路那样的多项式判定算法，则所有其它NP类问题也都能用多项式时间过程解决

ＮＰ-hard 问题

  • 哈密顿回路判定 (Hamiltonian Circuit )
  • 旅行推销员问题 (The Traveling Salesman problem)
  • 背包问题 (The Bin Packing problem)
  • 数独(Sudoku)

专家评论

  • Richard Karp: (Berkeley, unsure, P!=NP) My intuitive belief is that P is unequal to NP,but the only supporting arguments I can offer are the failure of all efforts to place specific NP-complete problems in P by constructing polynomial-time algorithms.I believe that the traditional proof techniques will not suffice. Something entirely novel will be required. My hunch is that the problem will be solved by a young researcher who is not encumbered by too much conventional wisdom about how to attack the problem.
  • Donald Knuth: (Retired from Stanford) It will be solved by either 2048 or 4096. I am currently somewhat pessimistic. The outcome will be the truly worst case scenario: namely that someone will prove “P=NP because there are only finitely many obstructions to the opposite hypothesis”; hence there will exists a polynomial time solution to SAT but we will never know its complexity!
  • Alexander Razborov: (Institute for Advanced Study) Well, this problem is (at the moment) very unique since we seem to be missing even the most basic understanding of the nature of its difficulty. Neither we currently have any ideas of what approach might turn out to be viable and lead us to the solution (or at least to a better understanding of the problem). All approaches tried so far probably (in some cases, provably) have failed. In this sense P=NP is different from many other major mathematical problems on which a gradual progress was being constantly done (sometimes for centuries) whereupon they yielded, either completely or partially. Perhaps, although, the key word in this difference is “century”, and the P=NP problem has simply not aged enough yet (by mathematical standards).
  • Bob Tarjan: (Princeton) In my view, there is no way to even make intelligent guesses about the answer to any of these questions. If I had to bet now, I would bet that P is not equal to NP. I estimate the half-life of this problem at 25 - 50 more years, but I wouldn’t bet on it being solved before 2100. Its solution will require unforeseen new techniques.
  • Avi Wigderson: (Institute of Advanced Study) I think this project is a bit premature. I think we know too little of what is relevant to even guess answers to your questions, certainly if “we” is replaced by “I.”The only thing I can definitely say, is that it is one of the most important and interesting questions ever asked by humans, and more people and resources should participate in filling up the holes that would allow better guesses of answers to your questions.
  • Andrew Yao（姚期智）: It’s hard to say when the question will be resolved. I don’t have even an educated guess. Probably the resolution is that P is not equal to NP. I think the mathematical techniques used will be beautiful.
  • Scott Aaronson: Look, this question of whether P=NP, what can I say? People like to describe it as “probably the central unsolved problem of theoretical computer science.” That’s a comical understatement. P vs. NP is one of the deepest questions that human beings have ever asked. And not only that: it’s one of the seven million-dollar prize problems of the Clay Math Institute! What an honor! Imagine: our mathematician friends have decided that P vs. NP is as important as the Hodge Conjecture, or even Navier-Stokes existence and smoothness! (Apparently they weren’t going to include it, until they asked around to make sure it was important enough.) Dude. One way to measure P vs. NP’s importance is this. If NP problems were feasible, then mathematical creativity could be automated. The ability to check a proof would entail the ability to find one. Every Apple II, every Commodore, would have the reasoning power of Archimedes or Gauss. So by just programming your computer and letting it run, presumably you could immediately solve not only P vs. NP, but also the other six Clay problems. (Or five, now that Poincaré is down.) Well, we certainly believe P≠NP. Indeed, we don’t even believe there’s a general way to solve NP problems that’s dramatically better than brute-force search through every possibility. The central challenge any P≠NP proof will have to overcome is to separate the NP problems that really are hard from the ones that merely look hard.

观点

  • P vs. NP 问题的解决可能有赖于大幅度创新的证明技术
  • 堵丁柱 & 葛可一的《计算复杂性导论》前言：
    • 人们在七十年代开始对NP-完全问题的研究主要是横向发展，也就是以许多不同的计算模型来分析难解问题的本质。这些新的计算模型包括了平行计算模型、概率计算模型、布尔线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。对这些新的计算模型的研究一方面使我们对难解问题有了更深一层的认识，一方面也产生了一些预想不到的应用。最显著的一个例子就是计算密码学的革命性突破：基于 NP 问题的公钥密码体系。另一个有名的例子是线性规划的多项式时间解的发现。
    • 到了八十年代中，对NP-完全问题的研究有了纵向的突破，在许多表面看来并不相关的计算模型之间发现了深刻的刻划关系。这些刻划关系不但解决了几个令人困扰多年的未解问题，同时也刺激了其它相关领域的发展。其中之一是对线路复杂性的研究发现了一些问题在某种有限制的线路模型中必有指数下界。这些结果使用了组合数学与概率方法等新的数学工具，并且解决了一个有名的有关多项式分层的未解问题。另一个更重大的结果是以概率可验证明对 NP 类的刻划。由此得出了许多组合优化问题近似解的NP-完全性，从而刺激了算法界对近似算法研究的新热潮。这个结果来自于对交互证明系统这个概念的扩展，并且使用了线性代数与编码理论等数学证明技巧。
  • 1993年 Razborov 和 Rudich 证明的一个结果表明，给定一个特定的可信的假设，在某种意义下「自然」的证明不能解决 P vs NP 问题。这表明一些现在似乎最有希望的方法不太可能成功。随着更多这类的定理得到证明，该定理的可能证明有越来越多的陷阱要规避。
  • In 1994, Alexander Razborov and Steven Rudich discovered the natural proofs barrier, which explained why previous attempts to prove P ≠ NP had failed.
  • Razborov and Rudich then proved their main result: A natural proof of P ≠ NP would require a very comprehensive understanding of how easy-to-compute and hard-to-compute functions differ, and that knowledge could also fuel a fast algorithm for spotting easy-to-compute functions even if they’re superficially complicated. If complexity theorists had succeeded in a natural proof of P ≠ NP, they would have discovered a nearly infallible way to glance at an arbitrary truth table and determine whether the corresponding function had high or low circuit complexity — a much stronger and more general result than they had set out to prove.