Lance Fortnow
ABSTRACT
Shortly after Steve Cook and Richard Karp showed the ex-istence of many natural NP-complete languages, researchers started to realize the great importance of the P versus NP problem and the difficulty of settling it. One graduate student at the Massachusetts Institute of Technology started to look beyond NP, asking what problems have a higher complexity and how do we classify them. Larry Stockmeyer discovered an amazing structure of complexity classes that continues to direct the research in complexity to this day. Stockmeyer passed away on July 31, 2004 at the age of 55 and in this paper we review some of his research and the legacy he has left on the community.
- S. Aaronson. The complexity zoo. http://complexityzoo.com.Google Scholar
- S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501--555, May 1998. Google ScholarDigital Library
- S. Arora and S. Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70--122, January 1998. Google ScholarDigital Library
- L. Babai. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computing, pages 421-429. ACM, New York, 1985. Google ScholarDigital Library
- L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36(2):254-276, 1988. Google ScholarDigital Library
- T. Baker, J. Gill, and R. Solovay. Relativizations of the P = NP question. SIAM Journal on Computing, 4(4):431-442, 1975.Google ScholarCross Ref
- M. Bellare, O. Goldreich, and E. Petrank. Uniform generation of NP-witnesses using an NP-oracle. Information and Computation, 163:510-526, 2000. Google ScholarDigital Library
- R. Boppana, J. Hastad, and S. Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25(2):127--132, 1987. Google ScholarDigital Library
- R. Boppana and M. Sipser. The complexity of finite functions. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, chapter 14, pages 757--804. North-Holland, 1990. Google ScholarDigital Library
- R. Britt. Universe measured: We're 156 billion light-years wide!, May 2004. Space.com.Google Scholar
- N. Bshouty, R. Cleve, R. Gavald'a, S. Kannan, and C. Tamon. Oracles and queries that are sufficient for exact learning. Journal of Computer and System Sciences, 52(3):421--433, June 1996. Google ScholarDigital Library
- J. Cai. Sp2⊆ZPPNP. In Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, pages 620--628. IEEE, New York, 2001. Google ScholarDigital Library
- A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28(1):114--133, 1981. Google ScholarDigital Library
- A. Chandra and L. Stockmeyer. Alternation. In Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, pages 98--109. IEEE, New York, 1976.Google Scholar
- S. Cook. The complexity of theorem-proving procedures. In Proceedings of the 3rd ACM Symposium on the Theory of Computing, pages 151--158. ACM, New York, 1971. Google ScholarDigital Library
- C. Dwork and L. Stockmeyer. Finite state verifiers I: The power of interaction. Journal of the ACM, 39(4):800--828, October 1992. Google ScholarDigital Library
- D. Eppstein. Computational complexity of games and puzzles. http://www.ics.uci.edu/~eppstein/cgt/hard.html.Google Scholar
- S. Even and R. Tarjan. A combinatorial problem which is complete in polynomial space. Journal of the ACM, 23(4):710--719, October 1976. Google ScholarDigital Library
- R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. Karp, editor, Complexity of computation, volume 7 of SIAM-AMS Proceedings, pages 43--73. Society for Industrial and Applied Mathematics, 1974.Google Scholar
- U. Feige, S. Goldwasser, L. Lovasz, S. Safra, and M. Szegedy. Interactive proofs and the hardness of approximating cliques. Journal of the ACM, 43(2):268--292, March 1996. Google ScholarDigital Library
- A. Fraenkel, M. Garey, D. Johnson, T. Schaefer, and Y. Yesha. The complexity of checkers on an N-N board. In Proceedings of the 19th IEEE Symposium on Foundations of Computer Science, pages 55--64. IEEE, New York, 1978.Google ScholarDigital Library
- M. Furst, J. Saxe, and M. Sipser. Parity, circuits and the polynomial-time hierarchy. Mathematical Systems Theory, 17:13--27, 1984.Google ScholarCross Ref
- M. Garey and D. Johnson. Computers and Intractability. A Guide to the theory of NP-completeness. W. H. Freeman and Company, New York, 1979. Google ScholarDigital Library
- O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(3):691--729, 1991. Google ScholarDigital Library
- S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems. SIAM Journal on Computing, 18(1):186--208, 1989. Google ScholarDigital Library
- S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 73--90. JAI Press, Greenwich, 1989.Google Scholar
- J. Hartmanis and R. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285--306, 1965.Google ScholarCross Ref
- J. H&229;stad. Almost optimal lower bounds for small depth circuits. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 143--170. JAI Press, Greenwich, 1989.Google Scholar
- N. Immerman. Nondeterministic space is closed under complementation. SIAM Journal on Computing,17(5):935-938, 1988. Google ScholarDigital Library
- M. Jerrum, A. Sinclair, and E. Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In Proceedings of the 33rd ACM Symposium on the Theory of Computing, pages 712--721. ACM, New York, 2001. Google ScholarDigital Library
- M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169--188, 1986. Google ScholarCross Ref
- J. Kadin. The polynomial time hierarchy collapses if the Boolean hierarchy collapses. SIAM Journal on Computing, 17(6):1263--1282, December 1988. Google ScholarDigital Library
- R. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, 1972.Google ScholarCross Ref
- R. Karp and R. Lipton. Some connections between nonuniform and uniform complexity classes. In Proceedings of the 12th ACM Symposium on the Theory of Computing, pages 302-309. ACM, 1980. Google ScholarDigital Library
- A. Klivans and D. van Melkebeek. Graph nonisomorhism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM Journal on Computing, 31(5):1501-1526, 2002. Google ScholarDigital Library
- K. Ko. Relativized polynomial time hierarchies having exactly k levels. SIAM Journal on Computing, 18:392--408, 1989. Google ScholarDigital Library
- J. Köbler and O. Watanabe. New collapse consequences of NP having small circuits. SIAM Journal on Computing, 28(1):311-324, February 1999. Google ScholarDigital Library
- D. Kozen. On parallelism in Turing machines. In Proceedings of the 17th IEEE Symposium on Foundations of Computer Science, pages 89-97. IEEE, New York, 1976.Google ScholarDigital Library
- L. Levin. Universal'nyie perebornyie zadachi (Universal search problems: in Russian). Problemy Peredachi Informatsii, 9(3):265--266, 1973. Corrected English translation in {64}.Google Scholar
- C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859--868, 1992. Google ScholarDigital Library
- A. Meyer and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In Proceedings of the 13th IEEE Symposium on Switching and Automata Theory, pages 125--129. IEEE, New York, 1972.Google ScholarDigital Library
- L. Meyer. Weak monadic second-order theory of successor is not elementary recursive. In Proceedings of the Boston University Logic Colloquium, volume 453 of Lecture Notes in Mathematics, pages 132--154. Springer, 1975.Google Scholar
- C. Papadimitriou. Games against nature. Journal of Computer and System Sciences, 31:288--301, 1985. Google ScholarDigital Library
- F. Pohl. Beyond the Blue Event Horizon. Ballantine Books, 1980. Chapter 12.Google Scholar
- J. Robson. N - N checkers is EXPTIME complete. SIAM Journal on Computing, 13(2):252--267, May 1984.Google Scholar
- A. Russell and R. Sundaram. Symmetric alternation captures BPP. Computational Complexity, 7(2):152--162, 1998. Google ScholarDigital Library
- W. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, pages 365--383, 1981.Google ScholarCross Ref
- W. Savitch. Relationship between nondeterministic and deterministic tape classes. Journal of Computer and System Sciences, 4:177--192, 1970.Google ScholarDigital Library
- M. Schaefer. Deciding the vapnik-chervonenkis dimension is -complete. Journal of Computer and System Sciences, 58:177-182, 1999. Google ScholarDigital Library
- M. Schaefer and C. Umans. Complete in the polynomial-time hierarchy: a compendium. SIGACT News, 33(3):32--49, September 2002.Google ScholarDigital Library
- T. Schaefer. On the complexity of some two-person perfect information games. Journal of Computer and System Sciences, 16:185--225, 1978.Google ScholarCross Ref
- R. Shaltiel and C. Umans. Pseudorandomness for approximate counting and sampling. In Proceedings of the 20th IEEE Conference on Computational Complexity. IEEE Computer Society, Los Alamitos, 2005. To appear. Google ScholarDigital Library
- A. Shamir. IP = PSPACE. Journal of the ACM, 39(4):869--877, 1992. Google ScholarDigital Library
- M. Sipser. Borel sets and circuit complexity. In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 61-69. ACM, New York, 1983. Google ScholarDigital Library
- M. Sipser. A complexity theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 330--335. ACM, New York, 1983. Google ScholarDigital Library
- L. Stockmeyer. The complexity of decision problems in automata theory and logic. PhD thesis, Massachusetts Institute of Technology, June 1974.Google Scholar
- L. Stockmeyer. The polynomial-time hierarchy. Theoretical Computer Science, 3:1--22, 1977.Google ScholarCross Ref
- L. Stockmeyer. On approximation algorithms for #P. SIAM Journal on Computing, 14(4):1--13, November 1985.Google ScholarCross Ref
- L. Stockmeyer and A. Chandra. Provably difficult combinatorial games. SIAM Journal on Computing, 8(2):151--174, May 1979.Google ScholarCross Ref
- L. Stockmeyer and A. Meyer. Word problems requiring exponential time. In Proceedings of the 5th ACM Symposium on the Theory of Computing, pages 1--9. ACM, New York, 1973. Google ScholarDigital Library
- L. Stockmeyer and A. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic. Journal of the ACM, 49(6):753-784, November 2002. Google ScholarDigital Library
- R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279--284, 1988. Google ScholarDigital Library
- S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM Journal on Computing, 20(5):865--877, 1991. Google ScholarDigital Library
- R. Trakhtenbrot. A survey of Russian approaches to Perebor (brute-force search) algorithms. Annals of the History of Computing, 6(4):384--400, 1984.Google ScholarDigital Library
- C. Umans. Hardness of approximating Σp2 minimization problems. In Proceedings of the 40th IEEE Symposium on Foundations of Computer Science, pages 465--474. IEEE, New York, 1999. Google ScholarDigital Library
- C. Umans. The minimum equivalent DNF problem and shortest implicants. Journal of Computer and System Sciences, 63(4):597--611, December 2001. Google ScholarDigital Library
- L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189--201, 1979.Google ScholarCross Ref
- L. Valiant. The complexity of reliability and enumeration problems. SIAM Journal on Computing, 8:410--421, 1979.Google ScholarCross Ref
- C. Wrathall. Complete sets and the polynomial-time hierarchy. Theoretical Computer Science, 3:23--33, 1977.Google ScholarCross Ref
- A. Yao. Separating the polynomial-time hierarchy by oracles. In Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, pages 1--10. IEEE, New York, 1985. Google ScholarDigital Library
Index Terms
- Beyond NP: the work and legacy of Larry Stockmeyer
Recommendations
The complexity of Boolean formula minimization
The Minimum Equivalent Expression problem is a natural optimization problem in the second level of the Polynomial-Time Hierarchy. It has long been conjectured to be @S"2^P-complete and indeed appears as an open problem in Garey and Johnson (1979) [5]. ...
Does the Polynomial Hierarchy Collapse if Onto Functions are Invertible?
Special Issue: Symposium on Computer Science, Guest Editors: Sergei Artemov, Volker Diekert and Dima GrigorievThe class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in ...
The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
We show that if the Boolean hierarchy collapses to level $k$, then the polynomial hierarchy collapses to $BH_{3}(k)$, where $BH_{3}(k)$ is the $k$th level of the Boolean hierarchy over $\Sigma^{P}_{2}$. This is an improvement over the known results, ...
Comments