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

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic