Degrees of sets having no subsets of higher m- and t t-degree

DOI10.3233/COM-200296OpenAlexW3128737888MaRDI QIDQ5859845

Patrizio Cintioli

Publication date: 18 November 2021

Published in: Computability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/com-200296

zbMATH Keywords

computably enumerable degreesmany-one reducibilitytruth-table reducibilityweak truth-table reducibilityhyperimmune degrees

Mathematics Subject Classification ID

Computability and recursion theory (03Dxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Classical recursion theory. Vol. II
• Upward closure and cohesive degrees
• Polynomial time introreducibility
• m-powers of simple sets
• On Kurtz randomness
• Three theorems on the degrees of recursively enumerable sets
• Sets without subsets of higher many-one degree
• Low sets without subsets of higher many-one degree
• Algorithmic Randomness and Complexity
• Asymptotic density, immunity and randomness
• Retraceable Sets
• Bi-immune sets for complexity classes
• Strong reducibilities
• Sets which do not have subsets of every higher degree
• Sets with no subsets of higher weak truth-table degree
• Mathematical Foundations of Computer Science 2003
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Sets with no subset of higher degree
• The degrees of bi‐immune sets
• Completeness, the Recursion Theorem, and Effectively Simple Sets
• Degrees in Which the Recursive Sets are Uniformly Recursive
• A Theorem on Hypersimple Sets