The importance of the P versus NP question

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The importance of the P versus NP question

Full text

Pdf (31 KB)

Source

Journal of the ACM (JACM) archive
Volume 50 , Issue 1 (January 2003) table of contents

Pages: 27 - 29

Year of Publication: 2003

ISSN:0004-5411

Author

Stephen Cook

University of Toronto, Toronto, Ont., Canada

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 23, Downloads (12 Months): 198, Citation Count: 1

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/602382.602398 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
	2	Baker, T., Gill, J., and Solovay, R. 1975. Relativizations of the P =? NP question. SICOMP: SIAM J. Comput.
	3	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	4	Gasarch, W. 2002. Guest column: The P=?NP poll. SIGACT NEWS 33, 2 (June), 34--47.
	5	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	6	Yuri Gurevich, Average case completeness, Journal of Computer and System Sciences, v.42 n.3, p.346-398, June 1991 [doi>10.1016/0022-0000(91)90007-R]
	7	Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Near-Optimal Conversion of Hardness into Pseudo-Randomness, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.181, October 17-18, 1999
	8	Levin, L. 1973. Universal search problems (in Russian). Problemy Peredachi Informatsii 9, 3, 265--266. (English translation in Trakhtenbrot, B. A.: A survey of Russian approaches to Perebor (brute-force search) algorithms. Ann. Hist. Comput. 6 (1984), 384--400.)
	9	Leonid A Levin, Average case complete problems, SIAM Journal on Computing, v.15 n.1, p.285-286, Feb. 1986 [doi>10.1137/0215020]
	10	Alexander A. Razborov , Steven Rudich, Natural proofs, Journal of Computer and System Sciences, v.55 n.1, p.24-35, Aug. 1997 [doi>10.1006/jcss.1997.1494]
	11	Robertson, N., and Seymour, P. D. 1983--1995. Graph minors i--xiii. J. Combinat. Theory B.
	12	Smale, S. 1998. Mathematical problems for the next century. MATHINT: The Mathematical Intelligencer 20.
	13	Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001