Switch to: Citations

Add references

You must login to add references.
  1. Effective Search Problems.Martin Kummer & Frank Stephan - 1994 - Mathematical Logic Quarterly 40 (2):224-236.
    The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
  • Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
  • Information- Theoretic Characterizations of Recursive Infinite Strings.A. Meyer - unknown
    Loveland and Meyer have studied necessary and sufficient conditions for an infinite binary string x to be recursive in terms of the programsize complexity relative to n of its n-bit prefixes xn. Meyer has shown that x is recursive iff ∃c, ∀n, K(xn/n) ≤ c, and Loveland has shown that this is false if one merely stipulates that K(xn/n) ≤ c for infinitely..
     
    Export citation  
     
    Bookmark   1 citation