Classifying the computational complexity of problems

DOI10.2307/2273858MaRDI QIDQ3781088zbMATH OpenOpenAlexFDO

Authors Larry J. Stockmeyer

Publication date 1987

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

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

zbMATH Keywords

bibliographycompletenesscomputational complexitydecidable setslower boundsreducibilitiessurvey

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)

Recommendations

• scientific article; zbMATH DE number 218387
• The complexity of satisfiability problems
• Reducibility among combinatorial problems
• An overview of computational complexity
• scientific article; zbMATH DE number 3888913

Cites work

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

Cited in

(25)

• Computational complexity of problems in classification according to a relation matrix
• The complexity of circuit value and network stability
• First-order linear logic without modalities is NEXPTIME-hard
• Abduction from logic programs: Semantics and complexity
• Logic programming and knowledge representation---The A-Prolog perspective
• Randomized proofs in arithmetic
• Weakly complete problems are not rare
• The intrinsic difficulty of recursive functions
• Circuit complexity of linear functions: gate elimination and feeble security
• Classification and complexity of problems.
• Double-exponential inseparability of Robinson subsystem \(Q_{+}\)
• Complexity of intuitionistic propositional logic and its fragments
• scientific article; zbMATH DE number 8764 (Why is no real title available?)
• scientific article; zbMATH DE number 139608 (Why is no real title available?)
• What is an inference rule?
• Decomposition representations of logical equations in problems of inversion of discrete functions
• scientific article; zbMATH DE number 218387 (Why is no real title available?)
• scientific article; zbMATH DE number 2086606 (Why is no real title available?)
• Separating Complexity Classes Using Autoreducibility
• Reducibility among combinatorial problems
• Capturing complexity classes with Lindström quantifiers
• scientific article; zbMATH DE number 7300350 (Why is no real title available?)
• The most nonelementary theory
• Circuit complexity before the dawn of the new millennium
• A uniform method for proving lower bounds on the computational complexity of logical theories

This page was built for publication: Classifying the computational complexity of problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3781088)