A uniform approach to define complexity classes
From MaRDI portal
Publication:1200807
DOI10.1016/0304-3975(92)90125-YzbMath0754.68049MaRDI QIDQ1200807
Pierluigi Crescenzi, Daniel P. Bovet, Riccardo Silvestri
Publication date: 16 January 1993
Published in: Theoretical Computer Science (Search for Journal in Brave)
\(C\)-classescomplete languages for relativized \(C\)-classesrelativized separation of \(C\)-classesstrong separation of relativized \(C\)-classes
Related Items
UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS, A characterization of the leaf language classes, Immunity and Simplicity for Exact Counting and Other Counting Classes, Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies, Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria, Reductions between disjoint NP-pairs, Languages polylog-time reducible to dot-depth 1/2, Unambiguous computations and locally definable acceptance types, Optimal proof systems imply complete sets for promise classes, Unnamed Item, On balanced versus unbalanced computation trees, Perfect correspondences between dot-depth and polynomial-time hierarchies, A characterization of definability of second-order generalized quantifiers with applications to non-definability, Hierarchies and reducibilities on regular languages related to modulo counting, Separating complexity classes with tally oracles, Succinct circuit representations and leaf language classes are basically the same concept, On the acceptance power of regular languages, Helping by unambiguous computation and probabilistic computation, Fine hierarchies and m-reducibilities in theoretical computer science, Approximate counting in bounded arithmetic, Quantum and classical complexity classes: Separations, collapses, and closure properties, Lower bounds and the hardness of counting properties, Leaf languages and string compression, Functions computable in polynomial space, Machines that can output empty words, Unnamed Item, The robustness of LWPP and WPP, with an application to graph reconstruction, Dot operators, THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS, Succinct representation, leaf languages, and projection reductions, On Existentially First-Order Definable Languages and Their Relation to NP, Relating polynomial time to constant depth, Nondeterministic \(NC^1\) computation, LINDSTRÖM QUANTIFIERS AND LEAF LANGUAGE DEFINABILITY, SELF-SPECIFYING MACHINES, Structures interpretable in models of bounded arithmetic, A model-theoretic characterization of the weak pigeonhole principle, A reducibility for the dot-depth hierarchy, Reducing the number of solutions of NP functions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The complexity of combinatorial problems with succinct input representation
- Complexity classes without machines: on complete languages for UP
- Probabilistic quantifiers and games
- Relativized Arthur-Merlin versus Merlin-Arthur games
- A uniform approach to obtain diagonal sets in complexity classes
- On counting problems and the polynomial-time hierarchy
- A second step toward the polynomial hierarchy
- Complexity classes and sparse oracles
- Immunity, Relativizations, and Nondeterminism
- A note on separating the relativized polynomial time hierarchy by immune sets
- Simplicity, Relativizations and Nondeterminism
- Immunity and simplicity in relativizations of probabilistic complexity classes
- The Boolean Hierarchy I: Structural Properties
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Alternation
- On the Structure of Polynomial Time Reducibility
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- On the power of parity polynomial time
