Classifying the computational complexity of problems

DOI10.2307/2273858zbMath0639.03041OpenAlexW2101017866MaRDI QIDQ3781088

Larry J. Stockmeyer

Publication date: 1987

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2273858

zbMATH Keywords

surveycomputational complexitybibliographycompletenesslower boundsreducibilitiesdecidable sets

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

First-order linear logic without modalities is NEXPTIME-hard, The most nonelementary theory, Weakly complete problems are not rare, The intrinsic difficulty of recursive functions, Capturing complexity classes with Lindström quantifiers, Abduction from logic programs: Semantics and complexity, Decomposition representations of logical equations in problems of inversion of discrete functions, What is an inference rule?, Circuit complexity of linear functions: gate elimination and feeble security, A uniform method for proving lower bounds on the computational complexity of logical theories, The complexity of circuit value and network stability, Randomized proofs in arithmetic, Double-exponential inseparability of Robinson subsystem Q₊, Complexity of intuitionistic propositional logic and its fragments, Unnamed Item, Logic programming and knowledge representation---The A-Prolog perspective

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• The complexity of two-player games of incomplete information
• The propositional dynamic logic of deterministic, well-structured programs
• BPP and the polynomial hierarchy
• A note on the parallel computation thesis
• Solitaire automata
• The complexity of facets (and some facets of complexity)
• Games against nature
• Complete problems in the first-order predicate calculus
• The complexity of elementary algebra and geometry
• Probabilistic algorithm for testing primality
• Complexity of Boolean algebras
• Hex ist Pspace-vollständig. (Hex is Pspace-complete)
• On uniform circuit complexity
• On time-space classes and their relation to the theory of real addition
• Complexity results for classes of quantificational formulas
• The complexity of logical theories
• The complexity of Presburger arithmetic with bounded quantifier alternation depth
• The maximum flow problem is log space complete for P
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• An observation on time-storage trade off
• Space-bounded reducibility among combinatorial problems
• A comparison of polynomial time reducibilities
• Translational lemmas, polynomial time, and \((\log n)^j\)-space
• Practical decidability
• On the equivalence, containment, and covering problems for the regular and context-free languages
• The network complexity and the Turing machine complexity of finite functions
• A characterization of the power of vector machines
• Riemann's hypothesis and tests for primality
• Relating refined space complexity classes
• The equality problem for vector addition systems is undecidable
• On the complexity of some two-person perfect-information games
• Linear programming is log-space hard for P
• The computational complexity of logical theories
• Propositional dynamic logic of regular programs
• A hierarchy for nondeterministic time complexity
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Structure and complexity of relational queries
• Time bounded random access machines
• Relationships between nondeterministic and deterministic tape complexities
• Parallel program schemata
• Das Repräsentantenproblem im Prädikatenkalkül der ersten Stufe mit Identität
• Weak Second‐Order Arithmetic and Finite Automata
• N by N Checkers is Exptime Complete
• Parity, circuits, and the polynomial-time hierarchy
• A taxonomy of problems with fast parallel algorithms
• On the sequential nature of unification
• An overview of computational complexity
• On the complexity of unique solutions
• The complexity of propositional linear temporal logics
• Hard-core theorems for complexity classes
• Combinatorics, complexity, and randomness
• The Complexity of Enumeration and Reliability Problems
• Provably Difficult Combinatorial Games
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Equivalences Among Relational Expressions with the Union and Difference Operators
• Probabilistic Algorithms in Finite Fields
• The Complexity of the Finite Containment Problem for Petri Nets
• Alternation
• Relativized Questions Involving Probabilistic Algorithms
• A universal interconnection pattern for parallel computers
• Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs
• A Decision Procedure for the First Order Theory of Real Addition with Order
• On Reducibility to Complex or Sparse Sets
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• On the Structure of Polynomial Time Reducibility
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• New problems complete for nondeterministic log space
• A Fast Monte-Carlo Test for Primality
• Fast Parallel Matrix Inversion Algorithms
• On Isomorphisms and Density of $NP$ and Other Complete Sets
• On Time Versus Space
• On Equivalence and Containment Problems for Formal Languages
• Computational Complexity of Probabilistic Turing Machines
• Separating Nondeterministic Time Complexity Classes
• On Relating Time and Space to Size and Depth
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• Computational Parallels between the Regular and Context-Free Languages
• Relations Among Complexity Measures
• Turing machines and the spectra of first-order formulas
• Paths, Trees, and Flowers
• A Machine-Independent Theory of the Complexity of Recursive Functions
• On Effective Procedures for Speeding Up Algorithms
• A Note Concerning Nondeterministic Tape Complexities
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide
• The NP-completeness column: An ongoing guide