beyond just the P versus NP problem
that I haven’t discussed here. In “
Further Reading,” a number of references
are presented for those interested in a
deeper understanding of the P versus
NP problem and computational complexity.
The P versus NP problem has gone
from an interesting problem related to
logic to perhaps the most fundamental
and important mathematical question
of our time, whose importance only
grows as computers become more powerful and widespread. The question has
even hit popular culture appearing in
television shows such as The Simpsons
and Numb3rs. Yet many only know of
the basic principles of P versus NP and
I hope this survey has given you a small
feeling of the depth of research inspired
by this mathematical problem.
Proving P ≠ NP would not be the end
of the story, it would just show that NP-
complete problem, don’t have efficient
algorithms for all inputs but many questions might remain. Cryptography, for
example, would require that a problem
like factoring (not believed to be NP-
complete) is hard for randomly drawn
composite numbers.
Proving P ≠ NP might not be the start
of the story either. Weaker separations
remain perplexingly difficult, for example showing that Boolean-formula Satisfiability cannot be solved in near-linear
time or showing that some problem
using a certain amount of memory cannot be solved using roughly the same
amount of time.
None of us truly understands the P
versus NP problem, we have only begun
to peel the layers around this increasingly complex question. Perhaps we will
see a resolution of the P versus NP
problem in the near future but I almost hope
not. The P versus NP problem continues
to inspire and boggle the mind and continued exploration of this problem will
lead us to yet even new complexities in
that truly mysterious process we call
computation.
further Reading
Recommendations for a more in-depth
look at the P versus NP problem and the
other topics discussed in this article:
Steve Homer and I have written a ˲
detailed historical view of computational complexity. 14
The 1979 book of Garey and John- ˲
son still gives the best overview of the P
versus NP problem with an incredibly
useful list of NP-complete problems. 16
Scott Aaronson looks at the unlikely ˲
possibility that the P versus NP problem
is formally independent. 1
Russell Impagliazzo gives a wonder- ˲
ful description of five possible worlds of
complexity. 22
Sanjeev Arora and Boaz Barak have ˲
a new computational complexity textbook with an emphasis on recent research directions. 5
The ˲ Foundations and Trends in Theoretical Computer Science journal and the
Computational Complexity columns of
the Bulletin of the European Association
of Theoretical Computer Science and
SI-GACT News have many wonderful surveys on various topics in theory including those mentioned in this article.
Read the blog Computational Com- ˲
plexity and you will be among the first to
know about any updates of the status of
the P versus NP problem. 13
acknowledgments
Thanks to Rahul Santhanam for many
useful discussions and comments. Josh
Grochow wrote an early draft. The anonymous referees provided critical advice.
Some of the material in this article has
appeared in my earlier surveys and my
blog. 13
References
1. Aaronson, s. Is P versus nP formally independent?
Bulletin of the European Association for Theoretical
Computer Science 81 (oct. 2003).
2. Agrawal, M., Kayal, n., and saxena, n. PRIMEs. In
Annals of Mathematics 160, 2 (2004) 781–793.
3. Applegate, D., Bixby, R., Chvátal, V., and Cook, W. on the
solution of traveling salesman problems. Documenta
Mathematica, Extra Volume ICM III (1998), 645–656.
4. Arora, s. Polynomial time approximation schemes for
Euclidean traveling salesman and other geometric
problems. J. ACM 45, 5 (sept. 1998), 753–782.
5. Arora, s. and Barak, B. Complexity Theory: A Modern
Approach. Cambridge University Press, Cambridge,
2009.
6. Baker, T., Gill, j., and solovay, R. Relativizations of the P
= nP question. SIAM Journal on Computing 4, 4 (1975),
431–442.
7. Cantor, G. Ueber eine Eigenschaft des Inbegriffes
aller reellen algebraischen Zahlen. Crelle’s Journal 77
(1874), 258–262.
8. Cipra, B. This Ising model is nP-complete. SIAM News
33, 6 (july/Aug. 2000).
9. Conitzer, V. and sandholm, T. new complexity results
about nash equilibria. Games and Economic Behavior
63, 2 (july 2008), 621–641.
10. Cook, s. The complexity of theorem-proving
procedures. In Proceedings of the 3rd ACM Symposium
on the Theory of Computing, ACM, ny, 1971, 151–158.
11. Downey, R. and Fellows, M. Parameterized Complexity.
springer, 1999.
12. Edmonds, j. Paths, trees and owers. Canadian Journal
of Mathematics 17, (1965), 449–467.
13. Fortnow, L. and Gasarch, W. Computational complexity;
http://weblog.fortnow.com.
14. Fortnow, L. and Homer, s. A short history of
computational complexity. Bulletin of the European
Association for Theoretical Computer Science 80,
(june 2003).
15. Furst, M., saxe, j., and sipser, M. Parity, circuits and
the polynomial-time hierarchy. Mathematical Systems
Theory 17 (1984), 13–27.
16. Garey, M. and johnson, D. Computers and Intractability.
A Guide to the Theory of NP-Completeness. W. H.
Freeman and Company, ny, 1979.
17. Goemans, M. and Williamson, D. Improved
approximation algorithms for maximum cut and
satisfiability problems using semidefinite programming.
Journal of the ACM 42, 6 (1995), 1115–1145.
18. Goldreich, o. Foundations of cryptography|a primer.
Foundations and Trends in Theoretical Computer
Science 1, 1 (2005) 1–116.
19. Grover, L. A fast quantum mechanical algorithm for
database search. In Proceedings of the 28th ACM
Symposium on the Theory of Computing. ACM, ny,
1996, 212–219.
20. Gusfield, D. Algorithms on Strings, Trees and
Sequences: Computer Science and Computational
Biology. Cambridge University Press, 1997.
21. Haken, A. The intractability of resolution. Theoretical
Computer Science, 39 (1985) 297–305.
22. Impagliazzo, R. A personal view of average-case
complexity theory. In Proceedings of the 10th Annual
Conference on Structure in Complexity Theory. IEEE
Computer society Press, 1995, 134–147.
23. Impagliazzo, R. and Wigderson, A. P = BPP if E requires
exponential circuits: Derandomizing the XoR lemma. In
Proceedings of the 29th ACM Symposium on the Theory
of Computing. ACM, ny, 1997, 220–229.
24. Karp, R. Reducibility among combinatorial problems.
Complexity of Computer Computations. R. Miller and j.
Thatcher, Eds. Plenum Press, 1972, 85–103.
25. Khot, s., Kindler, G., Mossel, E., and o’Donnell, R.
optimal inapproximability results for MAX-CUT and
other 2-variable CsPs? SIAM Journal on Computing
37, 1 (2007), 319–357.
26. Lathrop, R. The protein threading problem with
sequence amino acid interaction preferences is nP-complete. Protein Engineering 7, 9 (1994), 1059–1068.
27. Levin, L. Universal’nyie perebornyie zadachi (Universal
search problems: in Russian). Problemy Peredachi
Informatsii 9, 3 (1973), 265–266. Corrected English
translation. 37
28. Levin, L. Average case complete problems. SIAM
Journal on Computing 15, (1986), 285–286.
29. Mulmuley, K. and sohoni, M. Geometric complexity
theory I: An approach to the P vs. nP and related
problems. SIAM Journal on Computing 31, 2, (2001)
496–526.
30. Raghavendra, P. optimal algorithms and
inapproximability results for every csp? In Proceedings
of the 40th ACM Symposium on the Theory of
Computing. ACM, ny, 2008, 245–254.
31. Razborov, A. Lower bounds on the monotone
complexity of some Boolean functions. Soviet
Mathematics-Doklady 31, (1985) 485–493.
32. Razborov, A. on the method of approximations. In
Proceedings of the 21st ACM Symposium on the Theory
of Computing. ACM, ny, 1989, 167–176.
33. Razborov, A., and Rudich, s. natural proofs. Journal
of Computer and System Sciences 55, 1 (Aug. 1997),
24–35.
34. shor. P. Polynomial-time algorithms for prime
factorization and discrete logarithms on a quantum
computer. SIAM Journal on Computing 26, 5 (1997)
1484–1509.
35. solovay, R. and strassen, V. A fast Monte-Carlo test for
primality. SIAM Journal on Computing 6 (1977), 84–85.
see also erratum 7:118, 1978.
36. sudan, M. Probabilistically checkable proofs. Commun.
ACM 52, 3 (Mar. 2009) 76–84.
37. Trakhtenbrot, R. A survey of Russian approaches to
Perebor (brute-force search) algorithms. Annals of the
History of Computing 6, 4 (1984), 384–400.
38. Turing, A. on computable numbers, with an application
to the Etscheidungs problem. Proceedings of the
London Mathematical Society 42 (1936), 230–265.
39. van Melkebeek, D. A survey of lower bounds for
satisfiability and related problems. Foundations and
Trends in Theoretical Computer Science 2, (2007),
197–303.
Lance Fortnow ( fortnow@eecs.northwestern.edu) is a
professor of electrical engineering and computer science
at northwestern University’s McCormick school of
Engineering, Evanston, IL.