Differences between resource bounded degree structures

DOI10.1305/NDJFL/1082637612MaRDI QIDQ558725zbMATH OpenOpenAlexFDO

Authors Michael E. Mytilinaios, Theodore A. Slaman

Publication date 13 July 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/1082637612

zbMATH Keywords

polynomial-time degreetruth-table degreeTuring degree

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the structures inside truth-table degrees
• scientific article; zbMATH DE number 3869313
• Infimum properties differ in the weak truth-table degrees and the Turing degrees
• Relations between table-type degrees
• scientific article; zbMATH DE number 62443

Cites work

• scientific article; zbMATH DE number 4037840 (Why is no real title available?)
• scientific article; zbMATH DE number 3715539 (Why is no real title available?)
• Interpretability and Definability in the Recursively Enumerable Degrees
• On the Structure of Polynomial Time Reducibility
• On the theory of the PTIME degrees of the recursive sets
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory
• The Theory of the Degrees below 0 ′

Cited in

(1)

• Automorphisms of the truth-table degrees are fixed on a cone

This page was built for publication: Differences between resource bounded degree structures

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