The status of the P versus NP problem
Author:
Top Cited Papers
Open Access
- 1 September 2009
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 52 (9) , 78-86
Abstract
It's one of the fundamental mathematical problems of our time, and its importance grows with the rise of powerful computers.Keywords
This publication has 24 references indexed in Scilit:
- Probabilistically checkable proofsCommunications of the ACM, 2009
- New complexity results about Nash equilibriaGames and Economic Behavior, 2008
- A Survey of Lower Bounds for Satisfiability and Related ProblemsFoundations and Trends® in Theoretical Computer Science, 2007
- Foundations of Cryptography – A PrimerFoundations and Trends® in Theoretical Computer Science, 2005
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problemsJournal of the ACM, 1998
- Natural ProofsJournal of Computer and System Sciences, 1997
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- The protein threading problem with sequence amino acid interaction preferences is NP-completeProtein Engineering, Design and Selection, 1994
- The intractability of resolutionTheoretical Computer Science, 1985
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984