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 ( [e-mail]) is a professor of electrical engineering and computer science at northwestern University’s McCormick school of Engineering, Evanston, IL.