The complexity types of computable sets

DOI10.1016/0022-0000(92)90018-EMaRDI QIDQ1190982zbMATH OpenFDO

Authors Wolfgang Maass, Theodore A. Slaman

Publication date 27 September 1992

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

reducibilitycompletenessrandom access machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Recommendations

• Set-theoretic structure of computable sets
• scientific article; zbMATH DE number 5875139
• Kolmogorov complexity and computably enumerable sets
• Computability of Følner sets
• On the computational complexity of defining sets
• Publication:5749278
• Computability-Theoretic Complexity of Countable Structures
• Computably enumerable sets and related issues
• Computational Complexity Via Finite Types
• scientific article; zbMATH DE number 65741

Cites work

• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 4010508 (Why is no real title available?)
• scientific article; zbMATH DE number 17551 (Why is no real title available?)
• scientific article; zbMATH DE number 3476588 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• scientific article; zbMATH DE number 3594649 (Why is no real title available?)
• scientific article; zbMATH DE number 3637286 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A characterization of complexity sequences
• An Overview of the Theory of Computational Complexity
• Computational speed-up by effective operators
• Linear time transformations between combinatorial problems
• On the Structure of Polynomial Time Reducibility
• On the structure of sets in NP and other complexity classes
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• Time bounded random access machines
• “Helping”: several formalizations

Cited in

(7)

• The Complexity of Infinite Computations In Models of Set Theory
• scientific article; zbMATH DE number 65752 (Why is no real title available?)
• Computational Complexity Via Finite Types
• The Computational Complexity of Choice Sets
• The complexity of Tukey types and cofinal types
• scientific article; zbMATH DE number 4160709 (Why is no real title available?)
• Timed Sets, Functional Complexity, and Computability

This page was built for publication: The complexity types of computable sets

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