submited by

Style Pass

This page collects links around papers that try to settle the "P versus NP" question (in either way). Here are some links that explain/discuss this question: A clear formulation of the "P versus NP" question by Stephen Cook. Mathworld's page on "P versus NP" The Wikipedia page on "P versus NP" Michael Sipser has a survey paper on "The History and Status of the P versus NP question" (Proceedings of the 24th Annual ACM Symposium on the Theory of Computing, 1992, pp. 603-619). Christos Papadimitriou has written a retrospective on NP-completeness Lance Fortnow and Steve Homer: A Short History of Computational Complexity Scott Aaronson: Is P Versus NP Formally Independent? and NP-complete Problems and Physical Reality Avi Wigderson: P, NP and Mathematics - a computational complexity perspective For a correct solution of the "P versus NP" question, the Clay Mathematics Institute (CMI) will award a prize of $1.000.000. More information on this prize is available at http://www.claymath.org/millennium-problems.

Here is the outcome of an opinion poll on "P versus NP" conducted by William Gasarch. Here are the reasons why Oded Goldreich refuses to proof-read papers settling the "P versus NP" question. Here is what googlism thinks of "P versus NP" and "P=NP". Here is a parody of a typical comp.theory newsgroup discussion of a typical P=/!=NP proof. Here is Homer Simpson on "P versus NP" (picture #1 / #2) Here is a cartoon by Pavel Pudlak on "P versus NP" Here is a (youtube) movie on P and NP.

Read more win.tue.nl/~...