Order:
  1.  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  
  2.  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  
  3.  11
    Max and Min Limiters.James Owings, William Gasarch & Georgia Martin - 2002 - Archive for Mathematical Logic 41 (5):483-495.
    If and the function is partial recursive, it is easily seen that A is recursive. In this paper, we weaken this hypothesis in various ways (and similarly for ``min'' in place of ``max'') and investigate what effect this has on the complexity of A. We discover a sharp contrast between retraceable and co-retraceable sets, and we characterize sets which are the union of a recursive set and a co-r.e., retraceable set. Most of our proofs are noneffective. Several open questions are (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark