The recursion-theoretic structure of complexity classes

DOI10.1016/0304-3975(85)90217-8zbMATH Open0576.03025OpenAlexW2066107173MaRDI QIDQ1064320FDOQ1064320

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

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

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)

Cites Work

• On the Structure of Polynomial Time Reducibility
• Title not available (Why is that?)
• Title not available (Why is that?)
• A comparison of polynomial time reducibilities
• Title not available (Why is that?)
• Strong nondeterministic polynomial-time reducibilities
• Some Results on Tape-Bounded Turing Machines
• Space bounds for processing contentless inputs
• On the structure of sets in NP and other complexity classes
• A uniform approach to obtain diagonal sets in complexity classes
• A note on structure and looking back applied to the relative complexity of computable functions
• On splitting recursive sets
• Title not available (Why is that?)
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Inductive Logic Programming
• Title not available (Why is that?)
• Index sets and presentations of complexity classes
• Diagonalization, uniformity, and fixed-point theorems
• Title not available (Why is that?)
• Generality's price: Inescapable deficiencies in machine-learned programs
• Algorithms and Computation
• Gap-languages and log-time complexity classes
• Title not available (Why is that?)
• 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)