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 boundednessdiagonal classesfixed-point theorems for subrecursive classes

Mathematics Subject Classification ID

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