scientific article; zbMATH DE number 1747699

DOI10.1002/1521-3870(200204)48:3%3C367::AID-MALQ367%3E3.0.CO;2-HMaRDI QIDQ4530147zbMATH OpenFDO

Authors V. K. Bulitko

Publication date 7 October 2002

Full work available at URL https://doi.org/10.1002/1521-3870(200204)48:3%3C367::AID-MALQ367%3E3.0.CO;2-H

zbMATH Keywords

degreerecursively enumerable setssub-Turing reducibilities

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• The exact complexity of the infinite Post Correspondence Problem
• Reductions, completeness and the hardness of approximability
• Sub-Turing reducibilities of restricted complexity
• Sufficient-completeness, ground-reducibility and their complexity
• Bounded fixed-parameter tractability and reducibility
• scientific article; zbMATH DE number 4132145
• On the complexity-relativized strong reducibilities
• Solution of Post’s reduction problem and some other problems of the theory of algorithms. I
• BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
• Bounded reducibility for computable numberings

Cites work

• About Segment Complexity of Turing Reductions
• scientific article; zbMATH DE number 3995657 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)

Cited in

(13)

• On the complexity of postoptimality analysis of 0/1 programs
• Sub-Turing reducibilities of restricted complexity
• On a general method of constructing post reducibilities and the corresponding completeness criteria
• Sub-computabilities
• A Post's program for complexity theory.
• scientific article; zbMATH DE number 4156422 (Why is no real title available?)
• scientific article; zbMATH DE number 3914303 (Why is no real title available?)
• scientific article; zbMATH DE number 3981159 (Why is no real title available?)
• BOUNDS IN THE TURING REDUCIBILITY OF FUNCTIONS
• About Segment Complexity of Turing Reductions
• scientific article; zbMATH DE number 3995657 (Why is no real title available?)
• On the strongly bounded Turing degrees of simple sets
• Turing incomparability in Scott sets

This page was built for publication:

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