Diagonalization, uniformity, and fixed-point theorems

DOI10.1016/0890-5401(92)90040-MzbMath0768.68018MaRDI QIDQ1201287

Kenneth W. Regan

Publication date: 17 January 1993

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

uniform boundedness; diagonal classes; fixed-point theorems for subrecursive classes

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D20: Recursive functions and relations, subrecursive hierarchies

Related Items

The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory, Index sets and presentations of complexity classes, Gap-languages and log-time complexity classes

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item