Аннотация:
We discuss the structures of degrees under the Turing reducibility and the bounded Turing reducibilities, when the questions asked of the oracle are bounded by some natural conditions. We survey what is known about the algebraic structure and the complexity of the decision procedure for these degree structures. Typical algebraic questions include the existence of infima, distributivity, embeddings of partial orderings or lattices and extension of embedding problems.
Finally, we discuss some results and open problems concerning definability and the complexity of the decision problems for these degree structures.
|
