The recursion-theoretic structure of complexity classes

DOI10.1016/0304-3975(85)90217-8MaRDI QIDQ1064320zbMATH OpenOpenAlexFDO

Authors 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

gap languagerecursive languagesrecursively presentable classes

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4108743
• Gap-languages and log-time complexity classes
• scientific article; zbMATH DE number 3877163
• scientific article; zbMATH DE number 512854
• scientific article; zbMATH DE number 512990

Cites work

• scientific article; zbMATH DE number 3841832 (Why is no real title available?)
• scientific article; zbMATH DE number 3877163 (Why is no real title available?)
• scientific article; zbMATH DE number 3428547 (Why is no real title available?)
• scientific article; zbMATH DE number 3431764 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• A comparison of polynomial time reducibilities
• A note on structure and looking back applied to the relative complexity of computable functions
• A uniform approach to obtain diagonal sets in complexity classes
• On splitting recursive sets
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• Some Results on Tape-Bounded Turing Machines
• Space bounds for processing contentless inputs
• Strong nondeterministic polynomial-time reducibilities

Cited in

(17)

• Complexity classes as mathematical axioms. II
• Separating Complexity Classes Using Autoreducibility
• Hard-core theorems for complexity classes
• Exact Pairs for Abstract Bounded Reducibilities
• Ordinal complexity of recursive definitions
• scientific article; zbMATH DE number 4108743 (Why is no real title available?)
• scientific article; zbMATH DE number 4179364 (Why is no real title available?)
• Inductive Logic Programming
• scientific article; zbMATH DE number 3877163 (Why is no real title available?)
• Index sets and presentations of complexity classes
• Diagonalization, uniformity, and fixed-point theorems
• Generality's price: Inescapable deficiencies in machine-learned programs
• scientific article; zbMATH DE number 4131660 (Why is no real title available?)
• Algorithms and Computation
• Gap-languages and log-time complexity classes
• scientific article; zbMATH DE number 3353266 (Why is no real title available?)
• Structural properties of bounded relations with an application to NP optimization problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1064320)