A uniform approach to define complexity classes
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3814972 (Why is no real title available?)
- scientific article; zbMATH DE number 3917710 (Why is no real title available?)
- scientific article; zbMATH DE number 3930351 (Why is no real title available?)
- scientific article; zbMATH DE number 3943795 (Why is no real title available?)
- scientific article; zbMATH DE number 3988707 (Why is no real title available?)
- scientific article; zbMATH DE number 4074483 (Why is no real title available?)
- A note on separating the relativized polynomial time hierarchy by immune sets
- A second step toward the polynomial hierarchy
- A uniform approach to obtain diagonal sets in complexity classes
- Alternation
- Complexity classes and sparse oracles
- Complexity classes without machines: on complete languages for UP
- Immunity and simplicity in relativizations of probabilistic complexity classes
- Immunity, Relativizations, and Nondeterminism
- On counting problems and the polynomial-time hierarchy
- On the Structure of Polynomial Time Reducibility
- On the power of parity polynomial time
- Probabilistic quantifiers and games
- 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 Arthur-Merlin versus Merlin-Arthur games
- Simplicity, Relativizations and Nondeterminism
- The Boolean Hierarchy I: Structural Properties
- The complexity of combinatorial problems with succinct input representation
Cited in
(43)- A model-theoretic characterization of the weak pigeonhole principle
- Perfect correspondences between dot-depth and polynomial-time hierarchies
- Complexity classes as mathematical axioms. II
- Generic separations and leaf languages
- SELF-SPECIFYING MACHINES
- Separating complexity classes with tally oracles
- Hierarchies and reducibilities on regular languages related to modulo counting
- On Existentially First-Order Definable Languages and Their Relation to NP
- Relations among parallel and sequential computation models
- Lower bounds and the hardness of counting properties
- Functions computable in polynomial space
- Leaf languages and string compression
- On balanced versus unbalanced computation trees
- Dot operators
- Relating polynomial time to constant depth
- A characterization of the leaf language classes
- Nondeterministic NC^1 computation
- Optimal proof systems imply complete sets for promise classes
- Structures interpretable in models of bounded arithmetic
- Helping by unambiguous computation and probabilistic computation
- Fine hierarchies and m-reducibilities in theoretical computer science
- Succinct circuit representations and leaf language classes are basically the same concept
- Unambiguous computations and locally definable acceptance types
- Separation of complexity classes in Koiran's weak model
- The robustness of LWPP and WPP, with an application to graph reconstruction
- The robustness of LWPP and WPP, with an application to graph reconstruction
- Languages polylog-time reducible to dot-depth 1/2
- Succinct representation, leaf languages, and projection reductions
- Quantum and classical complexity classes: Separations, collapses, and closure properties
- Approximate counting in bounded arithmetic
- Machines that can output empty words
- Reducing the number of solutions of NP functions
- Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
- Lindström quantifiers and leaf language definability
- A reducibility for the dot-depth hierarchy
- scientific article; zbMATH DE number 7561757 (Why is no real title available?)
- Polynomial time machines equipped with word problems over algebraic structures as their acceptance criteria
- THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
- A characterization of definability of second-order generalized quantifiers with applications to non-definability
- UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS
- Immunity and Simplicity for Exact Counting and Other Counting Classes
- Reductions between disjoint NP-pairs
- On the acceptance power of regular languages
This page was built for publication: A uniform approach to define complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1200807)
