The Degrees of Conditional Problems
colorful horizontal rule

Su Gao

Abstract

In this paper we define and study conditional problems and their degrees. The main result is that the class of conditional degrees is a lattice extending the ordinary Turing degrees and it is dense. These properties are not shared by ordinary Turing degrees. We show that the class of conditional many-one degrees is a distributive lattice. We also consider properties of semidecidable problems and their degrees, which are analogous to r.e. sets and degrees.

Table of Contents

  1. Introduction
  2. Conditional Oracle Turing Computations
  3. The Degrees of Conditional Problems: Definitions
  4. The Upper and Lower Bounds for Conditional Degrees
  5. Density of Conditional Degrees
  6. Summary
    Acknowledgment
    References
This paper was published in The Journal of Symbolic Logic 59 (1994), 166-181.

Back to Su Gao's Homepage