The recursion-theoretic structure of complexity classes

DOI10.1016/0304-3975(85)90217-8zbMath0576.03025OpenAlexW2066107173MaRDI QIDQ1064320

Diana Schmidt

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90217-8

zbMATH Keywords

recursive languagesgap languagerecursively presentable classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (6)

Generality's price: Inescapable deficiencies in machine-learned programs ⋮ Exact Pairs for Abstract Bounded Reducibilities ⋮ Index sets and presentations of complexity classes ⋮ Gap-languages and log-time complexity classes ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Structural properties of bounded relations with an application to NP optimization problems

Cites Work

• Strong nondeterministic polynomial-time reducibilities
• 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
• Space bounds for processing contentless inputs
• A comparison of polynomial time reducibilities
• On splitting recursive sets
• On the Structure of Polynomial Time Reducibility
• Some Results on Tape-Bounded Turing Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The recursion-theoretic structure of complexity classes