7 found
Order:
  1.  9
    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.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  2.  67
    Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
    A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  3.  35
    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.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  4.  12
    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.
  5.  10
    Nondeterministic Bounded Query Reducibilities.Richard Beigel, William Gasarch & Jim Owings - 1989 - Annals of Pure and Applied Logic 41 (2):107-118.
  6.  54
    The Complexity of Oddan.Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl & Frank Stephan - 2000 - Journal of Symbolic Logic 65 (1):1 - 18.
    For a fixed set A, the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: $ODD^A_n = \{(x_1, \dots ,x_n): {\tt\#}^A_n(x_1, \dots, x_n) \text{is odd}\}$ and, for m ≥ 2, $\text{MOD}m^A_n = \{(x_1, \dots ,x_n):{\tt\#}^A_n(x_1, \dots ,x_n) \not\equiv 0 (\text{mod} m)\},$ where ${\tt\#}^A_n(x_1, \dots ,x_n) = A(x_1)+\cdots+A(x_n)$ . (We identify A(x) with χ A (x), where χ A is (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  7.  15
    The Complexity of ODDnA.Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy Mcnicholl & Frank Stephan - 2000 - Journal of Symbolic Logic 65 (1):1-18.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark