The P-versus-NP page

submited by
Style Pass
2021-07-20 13:00:06

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

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.

Leave a Comment