Beyond NP

2005/05/22 by Lance Fortnow · 5 citations
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #semigroups and automata theory #Computer science #Computational complexity theory #Natural (archaeology) #Algorithm #History

paper · doi:10.1145/1060590.1060609

openalex publication_date 2005/05/22 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/29

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.

Citations

• Relativizations of the P = ?NP Question
• The complexity of computing the permanent
• The equivalence problem for regular expressions with squaring requires exponential space
• On Approximation Algorithms for # P
• Probabilistic checking of proofs
• Games against nature
• The complexity of theorem-proving procedures
• On the complexity of some two-person perfect-information games
• Nondeterministic Space is Closed under Complementation
• On the hardness of approximating minimization problems
• Parity, circuits, and the polynomial-time hierarchy
• Algebraic methods for interactive proof systems
• N by N Checkers is Exptime Complete
• Interactive proofs and the hardness of approximating cliques
• The Complexity of Enumeration and Reliability Problems
• Proof verification and the hardness of approximation problems
• Cosmological lower bound on the circuit complexity of a small problem in logic
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Reducibility among Combinatorial Problems
• Random generation of combinatorial structures from a uniform distribution
• Alternation

Cited by

• Larry Stockmeyer [wikipedia]
• Symposium on Theory of Computing [wikipedia]