The complexity types of computable sets

DOI10.1016/0022-0000(92)90018-EzbMATH Open0746.68035MaRDI QIDQ1190982FDOQ1190982

Authors: Wolfgang Maass, Theodore A. Slaman 

Publication date: 27 September 1992

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

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

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)

Cites Work

• On the Structure of Polynomial Time Reducibility
• Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Time bounded random access machines
• Linear time transformations between combinatorial problems
• A characterization of complexity sequences
• Computational speed-up by effective operators
• An Overview of the Theory of Computational Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the structure of sets in NP and other complexity classes
• “Helping”: several formalizations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Title not available (Why is that?)
• Computational Complexity Via Finite Types
• The Computational Complexity of Choice Sets
• The complexity of Tukey types and cofinal types
• Title not available (Why is that?)
• Timed Sets, Functional Complexity, and Computability
• The Complexity of Infinite Computations In Models of Set Theory

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)