The status of the P versus NP problem

Abstract

It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.

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 cryptographyla 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.

Index Terms

• Mathematics of computing

• Social and professional topics

• Software and its engineering

• Theory of computation

  • Computational complexity and cryptography

    • Complexity classes

    • Problems, reductions and completeness

  • Design and analysis of algorithms

  • Logic

  • Models of computation

    • Computability