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

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

Latest revision as of 15:22, 18 June 2024

scientific article
Language Label Description Also known as
English
Classifying the computational complexity of problems
scientific article

    Statements

    Classifying the computational complexity of problems (English)
    0 references
    1987
    0 references
    survey
    0 references
    computational complexity
    0 references
    decidable sets
    0 references
    reducibilities
    0 references
    completeness
    0 references
    lower bounds
    0 references
    bibliography
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers