Differences between resource bounded degree structures

DOI10.1305/NDJFL/1082637612zbMATH Open1068.03034OpenAlexW1993066088MaRDI QIDQ558725FDOQ558725

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

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

zbMATH Keywords

Turing degreepolynomial-time degreetruth-table degree

Mathematics Subject Classification ID

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

Cites Work

• On the Structure of Polynomial Time Reducibility
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the theory of the PTIME degrees of the recursive sets
• Interpretability and Definability in the Recursively Enumerable Degrees
• The Theory of the Degrees below 0 ′
• The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory

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)