Index sets and presentations of complexity classes
From MaRDI portal
Publication:1366536
DOI10.1016/0304-3975(95)00146-8zbMath0877.68058OpenAlexW2063417677MaRDI QIDQ1366536
Publication date: 18 September 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(95)00146-8
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computing degrees of unsolvability
- The recursion-theoretic structure of complexity classes
- How to prove representation-independent independence results
- Index sets in the arithmetical hierarchy
- Diagonalizations over polynomial time computable sets
- A note on structure and looking back applied to the relative complexity of computable functions
- Unprovability of theorems of complexity theory in weak number theories
- On the structure of sets in NP and other complexity classes
- A uniform approach to obtain diagonal sets in complexity classes
- Logical number theory I. An introduction
- Almost everywhere high nonuniform complexity
- Diagonalization, uniformity, and fixed-point theorems
- The polynomial-time hierarchy
- Complete sets and the polynomial-time hierarchy
- Arithmetical hierarchy and complexity of computation
- Hardness vs randomness
- The use of lists in the study of undecidable problems in automata theory
- The Expressiveness of Simple and Second-Order Type Structures
- Bi-immune sets for complexity classes
- The position of index sets of identifiable sets in the arithmetical hierarchy
- Arithmetic theories for computational complexity problems
- Index Sets Universal for Differences of Arithmetic Sets
- On Isomorphisms and Density of $NP$ and Other Complete Sets
- Indexmengen und Erkennung Rekursiver Funktionen
- On “provable” analogs of and
- Reduction of an arbitrary diophantine equation to one in 13 unknowns
- On the cutting edge of relativization: The resource bounded injury method
- Relativized Polynomial Time Hierarchies Having Exactly K Levels
- Genericity and measure for exponential time
- Degrees of Unsolvability. (AM-55)
- On the Degrees of Index Sets
- On the Degrees of Index Sets. II
- Index sets of finite classes of recursively enumerable sets
- Classes of Recursive Functions and Their Index Sets
- Recursive Properties of Abstract Complexity Classes
- Recursive Predicates and Quantifiers
This page was built for publication: Index sets and presentations of complexity classes
