Indexings of subrecursive classes
From MaRDI portal
Publication:1140080
DOI10.1016/0304-3975(80)90017-1zbMath0435.03033MaRDI QIDQ1140080
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
03D15: Complexity of computation (including implicit computational complexity)
03D20: Recursive functions and relations, subrecursive hierarchies
Related Items
Characterizing programming systems allowing program self-reference, Polynomial time computations in models of ET, Some remarks on witness functions for nonpolynomial and noncomplete sets in NP, Diagonalizations over polynomial time computable sets, Simplicity, immunity, relativizations and nondeterminism, Remarks on recursion versus diagonalization and exponentially difficult problems, On p-creative sets and p-completely creative sets, Diagonalization, uniformity, and fixed-point theorems, On 1-truth-table-hard languages, Generality's price: Inescapable deficiencies in machine-learned programs, Logics for reasoning about cryptographic constructions, Meeting of the Association for Symbolic Logic, Madison, 1982
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
