Diagonalization, uniformity, and fixed-point theorems
type: Item
instance of: scholarly article
title: Diagonalization, uniformity, and fixed-point theorems
zbMATH Open document ID: 0768.68018
DOI: 10.1016/0890-5401(92)90040-M
author: Kenneth W. Regan
published in: Information and Computation
publication date: 1993-01-17T00:00:00Z
review text: New fixed-point theorems for subrecursive classes are derived, together with a widely applicable theorem on the uniformity of certain reductions. The present formulation extends the main theorem of \textit{U. Schöning} ``A uniform approach to obtain diagonal sets for complexity classes'' [Theor. Comput. Sci. 18, 95-103 (1982; Zbl 0485.68039)] to cases which involve infinitely many diagonal classes, and which allow each diagonal class to contain uncountably many members. The other theorem is similar to the ``uniform boundedness theorem'' of classical analysis, and extends work of J. Grollmann and A. Selman.
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03D20
zbMATH DE Number: 97530
zbMATH Keywords: uniform boundedness
zbMATH Keywords: fixed-point theorems for subrecursive classes
zbMATH Keywords: diagonal classes
MaRDI profile type: Publication
cites work: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
cites work: Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
cites work: A Machine-Independent Theory of the Complexity of Recursive Functions
cites work: Quasi-realtime languages
cites work: On splitting recursive sets
cites work: A note on structure and looking back applied to the relative complexity of computable functions
cites work: Q3893911
cites work: Nonconstructive tools for proving polynomial-time decidability
cites work: Q3328286
cites work: Complexity Measures for Public-Key Cryptosystems
cites work: On the Computational Complexity of Algorithms
cites work: Some Results on Tape-Bounded Turing Machines
cites work: Q3862379
cites work: Expressibility and Parallel Complexity
cites work: The NP-completeness column: An ongoing guide
cites work: Indexings of subrecursive classes
cites work: On the Structure of Polynomial Time Reducibility
cites work: Relativization of questions about log space computability
cites work: On the structure of sets in NP and other complexity classes
cites work: Q4153600
cites work: Remarks on recursion versus diagonalization and exponentially difficult problems
cites work: Q3312209
cites work: Q3762301
cites work: Q5573961
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Real-Time Definable Languages
cites work: Q3996430
cites work: Space-bounded hierarchies and probabilistic computations
cites work: The recursion-theoretic structure of complexity classes
cites work: Q3663288
cites work: A uniform approach to obtain diagonal sets in complexity classes
cites work: Q4040892
description: scientific article; zbMATH DE number 97530