Sets without subsets of higher many-one degree

DOI10.1305/ndjfl/1117755150zbMath1077.03025OpenAlexW2020372113MaRDI QIDQ2565991

Patrizio Cintioli

Publication date: 28 September 2005

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1117755150

zbMATH Keywords

computational complexitymany-one reducibilityKleene hierarchy

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Low sets without subsets of higher many-one degree, Degrees of sets having no subsets of higher m- and t t-degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A result relating disjunctive self-reducibility to P-immunity
• A comparison of polynomial time reducibilities
• Classical recursion theory. Vol. II
• Polynomial time introreducibility
• On the strength of Ramsey's theorem
• Three theorems on the degrees of recursively enumerable sets
• A maximal set which is not complete
• Retraceable Sets
• Bi-immune sets for complexity classes
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Sets which do not have subsets of every higher degree
• Mathematical Foundations of Computer Science 2003
• Sets with no subset of higher degree