huangyhg

Cook著名的的NP完全性文章：
The Complexity of Theorem Proving Procedures

Cook在其研究文章中，提出并证明了后来以其名字命名的Cook's Theorem(Cook定理)。关于Cook定理，可参见：
http://en.wikipedia.org/wiki/Cook%27s_theorem

简单而言，Cook证明了SAT(Boolean Satisfiability Problem)问题是一个NP完全性问题。

关于NP完全性问题的定义通常是：

一个可判定性问题C是NP完全的，如果：
1。这个问题是NP问题。
2。所有其他的NP问题可以归约为C问题。

关于NP， P问题，特别是著名的P=NP？的著名难题，可参见：
http://en.wikipedia.org/wiki/Comple...lasses_P_and_NP

关于各种计算复杂性问题的关系图，可参阅：
http://en.wikipedia.org/wiki/Complexity_class

P是否等价与NP的问题已经成为数学界，计算理论界的一个著名的难题。不管是谁能精确的证明P等价与NP，和P不等价与NP，他/她都可以获得百万美金的悬赏。(编者相信，他/她还会立刻得到图灵奖)。有兴趣的读者可参见：
http://www.claymath.org/millennium/

__________________
借用达朗贝尔的名言：前进吧，你会得到信心!
[url="http://www.dimcax.com"]几何尺寸与公差标准[/url]