Switch to: Citations

Add references

You must login to add references.
  1. On the complexity of finding the chromatic number of a recursive graph II: the unbounded case.Richard Beigel & William I. Gasarch - 1989 - Annals of Pure and Applied Logic 45 (3):227-246.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • A Theorem on Hypersimple Sets.J. C. E. Dekker - 1956 - Journal of Symbolic Logic 21 (1):100-100.
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Bounded query classes and the difference hierarchy.Richard Beigel, William I. Gasarch & Louise Hay - 1989 - Archive for Mathematical Logic 29 (2):69-84.
    LetA be any nonrecursive set. We define a hierarchy of sets (and a corresponding hierarchy of degrees) that are reducible toA based on bounding the number of queries toA that an oracle machine can make. WhenA is the halting problemK our hierarchy of sets interleaves with the difference hierarchy on the r.e. sets in a logarithmic way; this follows from a tradeoff between the number of parallel queries and the number of serial queries needed to compute a function with oracleK.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • On the complexity of finding the chromatic number of a recursive graph I: the bounded case.Richard Beigel & William I. Gasarch - 1989 - Annals of Pure and Applied Logic 45 (1):1-38.
    Download  
     
    Export citation  
     
    Bookmark   6 citations