About Segment Complexity of Turing Reductions

DOI10.1002/MALQ.19990450413MaRDI QIDQ4704660zbMATH OpenOpenAlexFDO

Authors V. K. Bulitko

Publication date 13 July 2000

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19990450413

zbMATH Keywords

hierarchy of relationsjump inversionKolmogorov complexityoracle Turing machinesuse restrictions on Turing reducibility

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Sub-Turing reducibilities of restricted complexity
• BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
• Anti-complex sets and reducibilities with tiny use
• scientific article; zbMATH DE number 1747699

Cites work

• A criterion for completeness of degrees of unsolvability

Cited in

(7)

• Query-monotonic Turing reductions
• 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000. La Sorbonne, Paris, France, July 23-31, 2000
• BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
• scientific article; zbMATH DE number 1747699 (Why is no real title available?)
• scientific article; zbMATH DE number 1408348 (Why is no real title available?)
• scientific article; zbMATH DE number 1421075 (Why is no real title available?)
• Anti-complex sets and reducibilities with tiny use

This page was built for publication: About Segment Complexity of Turing Reductions

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