scientific article; zbMATH DE number 1390013

MaRDI QIDQ4934278zbMATH OpenFDO

Authors Piergiorgio Odifreddi

Publication date 27 September 2000

zbMATH Keywords

degreestrong reducibilitysurvey

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Other degrees and reducibilities in computability and recursion theory (03D30)

Review text

This is a nice overview of old and recent results on strong reducibility in recursion theory. Relationships between many reducibilities and their degree structures are described considering both global and local properties. In the final part a discussion of open problems is given. The paper is recommended to specialists in recursion theory as well as to young researchers seeking for interesting and important tasks in the field. For the entire collection see [Zbl 0923.03001].

Recommendations

• scientific article; zbMATH DE number 1531931
• On restricted forms of enumeration reducibility
• Structures of some strong reducibilities
• Strong Positive Reducibilities
• T-Degrees, Jump Classes, and Strong Reducibilities

Cited in

(31)

• Reductive modes
• Quasi-injective reductions
• Reductivity
• Non-uniform reductions
• Strong Medvedev reducibilities and the KL-randomness problem
• \(Q\)-reducibility and \(m\)-reducibility on computably enumerable sets
• Polynomial clone reducibility
• Value-free reductions
• On a general method of constructing post reducibilities and the corresponding completeness criteria
• Constant Depth Reducibility
• scientific article; zbMATH DE number 3858462 (Why is no real title available?)
• REDUCTION PROBLEMS IN EXPERIMENTAL INVESTIGATIONS
• Guyan reduction
• Reduction Under Substitution
• Structures of some strong reducibilities
• Finding Reductions Automatically
• Strong Positive Reducibilities
• scientific article; zbMATH DE number 3943800 (Why is no real title available?)
• Reduced direct products
• Robust reductions
• scientific article; zbMATH DE number 510792 (Why is no real title available?)
• A New Reducibility between Turing‐ and wtt‐Reducibility
• On reduction properties
• scientific article; zbMATH DE number 701112 (Why is no real title available?)
• Intrinsic Reducibilities
• scientific article; zbMATH DE number 1531931 (Why is no real title available?)
• scientific article; zbMATH DE number 1390028 (Why is no real title available?)
• Analog reducibility
• scientific article; zbMATH DE number 2213919 (Why is no real title available?)
• On the complexity-relativized strong reducibilities
• Fine hierarchies and m-reducibilities in theoretical computer science

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 Q4934278)