Diagonalization, uniformity, and fixed-point theorems
From MaRDI portal
Publication:1201287
DOI10.1016/0890-5401(92)90040-MzbMath0768.68018MaRDI QIDQ1201287
Publication date: 17 January 1993
Published in: Information and Computation (Search for Journal in Brave)
Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursive functions and relations, subrecursive hierarchies (03D20)
Related Items
Index sets and presentations of complexity classes, Gap-languages and log-time complexity classes, The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space-bounded hierarchies and probabilistic computations
- The recursion-theoretic structure of complexity classes
- Indexings of subrecursive classes
- Remarks on recursion versus diagonalization and exponentially difficult problems
- A note on structure and looking back applied to the relative complexity of computable functions
- On the structure of sets in NP and other complexity classes
- A uniform approach to obtain diagonal sets in complexity classes
- On splitting recursive sets
- Graph minors. II. Algorithmic aspects of tree-width
- Complexity Measures for Public-Key Cryptosystems
- Nonconstructive tools for proving polynomial-time decidability
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- On the Structure of Polynomial Time Reducibility
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Relativization of questions about log space computability
- Expressibility and Parallel Complexity
- On the Computational Complexity of Algorithms
- Real-Time Definable Languages
- A Machine-Independent Theory of the Complexity of Recursive Functions
- Quasi-realtime languages
- Some Results on Tape-Bounded Turing Machines
- The NP-completeness column: An ongoing guide
