The history and status of the P versus NP question

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The history and status of the P versus NP question

Full text

Pdf (1.68 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 603 - 618

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Michael Sipser

Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 122, Citation Count: 7

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/129712.129771 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.

	Aj83	M. AJTAI, #-formulae on finite structures, Annals of Pure and Applied Logic 24, 1-48, 1983.
	AB87	N. Alon , R. B. Boppana, The monotone circuit complexity of Boolean functions, Combinatorica, v.7 n.1, p.1-22, Jan. 1987 [doi>10.1007/BF02579196]
	An85	A.E. ANDREEV, On a method for obtaining lower bounds for the complexity of individual monotone functions, Doklady Akademii Nauk SSSR 282:5, 1033-1037 (in Russian). English translation in Soviet Mathematics DoUady 31:3, 530-534, 1985.
	As55	G. ASSER, Das Repr#entatenproblem im PrKdikatenkalkiil der ersten Stufe mit identit#t, Zeitschrift fiir Matemitische Logic und Grundlagen der Mathematik, 1, 252-263, 1955.
	BGS75	T. P. BAKER, J. GILL, AND R. SOLOVAY, Relativizations of the P=?NP question, SIAM Journal on Computing 4:4, 431-442, 1975.
	Ba86a	David A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences, v.38 n.1, p.150-164, February 1989 [doi>10.1016/0022-0000(89)90037-8]
	Ba86a	D.A. BARRINQTON, A note on a theorem of Razborov, manuscript, 1986.
	BH91	S. BEN-DAVID AND S. HALEVI, On the independence of P versus NP, Tech. Report #699, Technion, 1991.
	Be82	S.J. BERKOWITZ, On some relationships between monotone and non-monotone circuit complexity, Technical Report, Computer Science Department, University of Toronto, 1982.
	Bl67	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	Bl84	N. BLUM, A Boolean function requiring 3n network size, Theoretical Computer Science 28, 337-345, 1984.
	Bo86	Ravi B Boppana, Threshold functions and bounded depth monotone circuits, Journal of Computer and System Sciences, v.32 n.2, p.222-229, April 1986 [doi>10.1016/0022-0000(86)90027-9]
	BS90	Ravi B. Boppana , Michael Sipser, The complexity of finite functions, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	Bu86	S.R. Buss, Bounded Arilhmetic, Bibliopolis, 1986.
	Co64	A. COBHAM, The intrinsic computational difficulty of functions, Proc. of the 196# international Congress for Logic, Methodology, and lhe Philosophy of Science, edited by Y. Bar- Hillel, North-Holland, 24-30, 1964.
	CSV84	A. K. CHANDRA, L. J. STOCKMEYER, AND U. VISHKIN, Constant depth reducibility, SIAM Journal on Compufiug 13:2, 423-439, 1984.
	Co71	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]
	Co75	Stephen A. Cook, Feasibly constructive proofs and the propositional calculus (Preliminary Version), Proceedings of seventh annual ACM symposium on Theory of computing, p.83-97, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803756]
	CU88	S.A. COOK AND A. URQUHART, Functional interpretations of feasibly constructive arithmetic, Technical Report 210/88, Computer Science Department, University of Toronto, 1988.
	DL79	Richard A. DeMillo , Richard J. Lipton, Some connections between mathematical logic and complexity theory, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.153-159, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804408]
	Du88	P. E. Dunne, The complexity of Boolean networks, Academic Press Professional, Inc., San Diego, CA, 1988
	Ed65	J. EDMONDS, Paths, trees, and flowers, Canadian Journal of Mathematics, 17, 449- 467, 1965.
	Ed65b	J. EDMONDS, Minimum partition of a matroid into independent sets, Journal of Research of the National Bureau of Standards (B), 69, 67-72,
	EIRS91	Jeff Edmonds , Russell Impagliazzo , Steven Rudich , Jiří Sgall, Communication complexity towards lower bounds on circuit depth, Proceedings of the 32nd annual symposium on Foundations of computer science, p.249-257, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185375]
	Fa74	R. FAaIN, Generalized first-order spectra and polynomial-time recognizable sets, Complexity of Computation, SIAM-AMS Proceedings 7, 43-73, 1974.
	FS88	Lance Fortnow , Michael Sipser, Are there interactive protocols for CO-NP languages?, Information Processing Letters, v.28 n.5, p.249-251, Aug. 12, 1988 [doi>10.1016/0020-0190(88)90199-8]
	FSS84	M. FURST, J. SAX#., AND M. SIr'SER, Parity, circuits and the polynomial time hierarchy, Mathematical Systems Theory 17, 13-27, 1984.
	Ga77	Z. GALm, On the complexity of regular resolution and the Davis-Putnam procedure, Theoretical Computer Science 4, 23-46, 1977.
	GJ79	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
	GH89	M. Goldmann, J. Hhstad, A lower bound for monotone clique using a communication game, manuscript, 1989.
	GS90	Michelangelo Grigni , Michael Sipser, Monotone complexity, Poceedings of the London Mathematical Society symposium on Boolean function complexity, p.57-75, December 1992, London, United Kingdom
	GS91	M. GrUGNI AND M. SIPSZR, Monotone separation of N C1 from logspaee, Proceedings of the 6th Annual Symposium on Structure in Complexity Theory, 294-298, 1991.
	HS72	L.H. HARPER AND J. E. SAVAGE, The complexity of the marriage problem, Advances in Mathematics 9, 299-312, 1972.
	Ha89	J. HARTMANIS, GSdel, von Neumann and the P=?NP Problem, Bulletin of the European Association for Theoretical Computer Science, 101-107, June 1989.
	HH76	J. Hartmanis , J. E. Hopcroft, Independence results in computer science, ACM SIGACT News, v.8 n.4, p.13-24, October-December 1976 [doi>10.1145/1008335.1008336]
	HS65	J. HARTMANIS AND P#. E. STEARNS, On the computational complexity of algorithms, Transactions of the AMS 117, 285-306, 1965.
	Ha85	A. HAKe, N, The intractability of resolution, Theoretical Computer Science 39, 297-308, 1985.
	Hå86	Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987
	HW91	J. H),STAD, A. WmD#.RSON, Composition of the Universal Relation, manuscript, 1991.
	HU79	John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	Im87	Neil Immerman, Languages that capture complexity classes, SIAM Journal on Computing, v.16 n.4, p.760-778, Aug. 1987 [doi>10.1137/0216051]
	Im88	Neil Immerman, Nondeterministic space is closed under complementation, SIAM Journal on Computing, v.17 n.5, p.935-938, October 1988 [doi>10.1137/0217058]
	JS74	N.D. JONES AND A. L. SELMAN, Turing machines and the spectra of first-order formulas, Journal of Symbolic Logic 39, 139-150, 1974.
	KS87	B. KALYANASUNDARAM AND G. SCHNIT- GER, The probabilistic communication complexity of set intersection, Proceedings of #he Second Annual Conference on Structure in Complexity Theory, 41-49, 1987.
	KRW91	M. KARCHMER, R. RAZ, A. WIGDERSON, On proving super-logarithmic depth lower bounds via the direct sum in communication complexity, Proceedings of the Sixth Annual Conference on Structure in Complexity Theory, 1991.
	KW88	Mauricio Karchmer , Avi Wigderson, Monotone circuits for connectivity require super-logarithmic depth, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.539-550, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62265]
	Ka72	R.M. KARP, Reducibility among combinatorim problems, Complexity of Computer Computations, Plenum Press, 85-103, 1972.
	Ko77	D. KOZEN, Lower bounds for natural proof systems, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, 254-266, 1977.
	LJK87	K. J. Lange , B. Jenner , B. Kirsig, The logarithmic alternation hierarchy collapses: A&Sgr;L-2- = A&Pgr;L-2-, 14th International Colloquium on Automata, languages and programming, p.531-541, July 1987, Karlsruhe, Germany
	Le05	H. L#.B#.SGU#., Sur les fonetions repr#sentables analytiquement, Journal de Math. 6# serie 1, 139-216, 1905.
	Le73	L. LEVIN, Universal sequential search problems, Probl. Pered. Inform. IX 3, 1973; translation in Problems of Information Trans 9, 3, 265--266; corrected translation in Trakhtenxbrot {Tr84}.
	Li78	R.J. LIPTON, Model theoretic aspects of complexity theory, Proceeding of the 19th Annual Symposium on Foundations of Computer Science, 193-200, 1978.
	LFKN90	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	MS72	A. R,. MEYER, AND L. J. STOCKMEYER, The equivalence problem for regular expressions with squaring requires exponential time, Proceedings of #he 13th Annual Symposium on Switching and Automata Theory, 125-129, 1972.
	Mo80	Y.N. MOSCHOVAKIS, Descriptive Set Theory, North-Holland, 1980.
	Mu56	D. E. MULLER, Complexity in electronic switching circuits, IRE Transactions on Electronic Computers 5, 15-19, 1956.
	Pa76	M. S. PATERSON, An introduction to Boolean function complexity, Astgrisque 38- 39, 183-201, 1976.
	Ra60	M.O. I#BIN, Degree of diflieutly of computing a function and a partial ordering of reeursive sets, Teeh. Rep. No. 2, Hebrew University, 1960.
	Ra66	M.O. tL#BIN, Mathematical theory of automata, Proceedings of 19th A CM Symposium in Applied Mathematics, 153-175, 1966.
	RW90	R. Raz , A. Wigderson, Monotone circuits for matching require linear depth, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.287-292, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100253]
	Ra85a	A. A. RAZBOROV, A lower bound on the monotone network complexity of the logical permanent, Matematicheskie gametki 37:6, 887-900 (in Russian). En/#lish translation in Mathematical Notes of the Academy of Sciences of the USSR 37:6, 485-493, 1985.
	Ra85b	A. A. RAZBOROV, A lower bound on the monotone network complexity of the logical permanent, Matema#icheskie Zametki 37:6, 887-900 (in Russian). English translation in Mathematical Notes of the Academy of Sciences of the USSR 37:6, 485--493, 1985.
	Ra87	A.A. RAZBOROV, Lower bounds on the size of bounded depth networks over a complete basis with logical addition, Matematicheskie Zametki 41:4, 598-607 (in Russian). English translation in Mathematical Notes of the Academy of Sciences of the USSR 41:4, 333- 338, 1987.
	Ra89	A. A. Razborov, On the method of approximations, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.167-176, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73023]
	Ra90a	A. A. Razborov, On the distributional complexity of disjointness, Proceedings of the seventeenth international colloquium on Automata, languages and programming, p.249-253, July 1990, Warwick University, England
	Ra90b	A. A. RAZBOROV, Applications of matrix methods for the theory of lower bounds in computational complexity, Combinalorica 10, 81-93, 1990.
	Sa72	J. E. Savage, Computational Work and Time on Finite Machines, Journal of the ACM (JACM), v.19 n.4, p.660-674, Oct. 1972 [doi>10.1145/321724.321731]
	Sa80	Vladimir Yu. Sazonov, A Logical Approach to the Problem "P=NP?", Proceedings of the 9th Symposium on Mathematical Foundations of Computer Science, p.562-575, September 01-05, 1980
	Sc52	H. SCHOLZ, Problem #1, Journal of Symbolic Logic, 17, 160, 1952.
	Sh90	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	Sh49	C.E. SHANNON, The synthesis of twoterminal switching circuits, Bell Systems Technical Journal 28:1, 59-98, 1949.
	Si81	M. SIPSZR, On polynomial vs. exponential growth, unpubfished, 1981.
	Si83	Michael Sipser, Borel sets and circuit complexity, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.61-69, December 1983 [doi>10.1145/800061.808733]
	Si84	M. SIPSER, A topological view of some problems in complexity theory, Colloquia Mathematica Societatis Jdno8 Bolyai 44, 387-391, 1984.
	Sm87	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
	Sz88	R. Szelepcsényi, The method of forced enumeration for nondeterministic automata, Acta Informatica, v.26 n.3, p.279-284, Nov. 1988 [doi>10.1007/BF00299636]
	Ta88	TARDOS, The gap between monotone and non-monotone circuit complexity is exponential, Combinatorica 8:1, 141-142, 1988.
	Tr84	B.A. TRAKHTBNBROT, A survey of Russian approaches to Perebor (brute-force search) algorithms, Annals of the History of Computing 6, no. 4, 384-400, 1984.
	Ts62	G.S. TSI#ITIN, On the complexity of derivation in propositional calculus, Studies in Constructive Mathematics and Mathematical Logic, Part 2, Consultants Bureau, New Youk-London, 115-125, 1962.
	Va90	Leslie G. Valiant, Why is Boolean complexity theory difficult?, Poceedings of the London Mathematical Society symposium on Boolean function complexity, p.84-94, December 1992, London, United Kingdom
	Vo53	J. VON NEUMANN, A certain zero-sum twoperson game equivalent to the optimal assignment problem, Contributions to the Theory of Games $, 5-12, 1953.
	We87	Ingo Wegener, The complexity of Boolean functions, John Wiley & Sons, Inc., New York, NY, 1987
	Ya59a	S. YABLONSKI, The algorithmic difficulties of synthesizing minimal switching circuits, Prob. lemy Kibernetiki 2, Moscow, Fizmatgiz, 75- 121, 1959; translation in Problems of Cybernetics 2, Pergamon Press, 401-457, 1961.
	Ya59b	S. YABLONSKI, On the impossibility of eliminating brute force search in solving some problems of circuit theory, Doklady, AN SSSR 124, 44-47, 1959.
	Ya85	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

CITED BY 7

	László Babai, Paul Erdös (1913-996): his influence on the theory of computing, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.383-401, May 04-06, 1997, El Paso, Texas, United States
	Lane A. Hemaspaandra , Kulathur S. Rajasethupathy , Prasanna Sethupathy , Marius Zimand, Power balance and apportionment algorithms for the United States Congress, Journal of Experimental Algorithmics (JEA), 3, p.1-es, 1998
	Scott Aaronson, Guest Column: NP-complete problems and physical reality, ACM SIGACT News, v.36 n.1, March 2005
	Phillip G. Bradford, Language constrained graph problems: a microcosm of engineering research and development, Proceedings of the 2nd WSEAS International Conference on Computer Engineering and Applications, p.71-76, January 25-27, 2008, Acapulco, Mexico
	Peter W. Shor, Progress in Quantum Algorithms, Quantum Information Processing, v.3 n.1-5, p.5-13, October 2004
	Peter Golbus , Robert W. McGrail , Tomasz Przytycki , Mary Sharac , Aleksandar Chakarov, Tricolorable torus knots are NP-complete, Proceedings of the 47th Annual Southeast Regional Conference, March 19-21, 2009, Clemson, South Carolina
	Alexandru-Liviu Olteanu, A tool for comparing resource-constrained project scheduling problem algorithms, Proceedings of the 9th WSEAS international conference on Applied informatics and communications, p.182-186, August 20-22, 2009, Moscow, Russia