The P versus NP Problem

P vs NP  Problem
Problem Statement. Does P = NP?
P = {L | L = L(M) for some Turing machine M that runs in polynomial time}.
The notation NP stands for “Nondeterministic Polynomial time”, since originally NP 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, P is the set of easy decision problems. NP 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 P are the problems where it’s easy to find a solution, and in NP are the problems where it’s easy to check a solution that may have been very tedious to find.
The crucial question related to P and NP is whether the subset relation is proper?
P ⊂ NP?
很显然的是P类都属于NP类(P ⊆ NP),这样问题就变成:是否某些NP类问题(比如旅行推销员问题)不存在多项式时间过程算法? 问题难在如何证明这一点?如何从逻辑上排除旅行推销员问题存在多项式时间过程算法的可能性?这跟黎曼假设的严格数学证明要排除临界线外有复零点的可能性一样困难。
复杂性范畴之间的包含关系:
LOGSPACE ⊆ P ⊆ NP ⊆ PSPACE,用简单的对角化论证法能够证明LOGSPACE是PSPACE的真子集,其余的包含关系是否为真包含关系?无人能够证明。
很多研究复杂性理论的专家都认为 P≠NP,MIT的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,那么机器就能给出克雷数学研究所七大难题的形式化证明,尽管证明会很繁琐很冗长。
在克雷数学研究所的官方资料中,此问题由 Stephen Cook (创造性地提出 NP-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类问题也都能用多项式时间过程解决
ζ NP-hard 问题
ξ 哈密顿回路判定 (Hamiltonian Circuit )
ξ 旅行推销员问题 (The Traveling Salesman problem)
ξ 背包问题 (The Bin Packing problem)
Advertisements

Tags:

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: