Indexings of subrecursive classes

DOI10.1016/0304-3975(80)90017-1zbMath0435.03033OpenAlexW2077694941MaRDI QIDQ1140080

Dexter Kozen

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90017-1

zbMATH Keywords

diagonalizationGödel numberingsubrecursive complexitysubrecursive indexing

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items

Some remarks on witness functions for nonpolynomial and noncomplete sets in NP ⋮ Generality's price: Inescapable deficiencies in machine-learned programs ⋮ Diagonalizations over polynomial time computable sets ⋮ Simplicity, immunity, relativizations and nondeterminism ⋮ A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff ⋮ Remarks on recursion versus diagonalization and exponentially difficult problems ⋮ On p-creative sets and p-completely creative sets ⋮ Meeting of the Association for Symbolic Logic, Madison, 1982 ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Logics for reasoning about cryptographic constructions ⋮ Characterizing programming systems allowing program self-reference ⋮ On 1-truth-table-hard languages ⋮ Polynomial time computations in models of ET ⋮ Intensional Kleene and Rice theorems for abstract program semantics ⋮ Subrecursive equivalence relations and (non-)closure under lattice operations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A comparison of polynomial time reducibilities
• Polynomial and abstract subrecursive classes
• On the density of honest subrecursive classes
• Nonexistence of program optimizers in several abstract settings
• Extension of an effectively generated class of functions by enumeration
• On the Structure of Polynomial Time Reducibility
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Algebraically Generalized Recursive Function Theory
• Construction of models for algebraically generalized recursive function theory
• Subrecursive Programming Languages, Part I
• Classes of Recursively Enumerable Sets and Their Decision Problems