Classifying the computational complexity of problems (Q3781088): Difference between revisions

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