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  
     
    Export citation  
     
    Bookmark   6 citations  
  • A proof of Beigel's cardinality conjecture.Martin Kummer - 1992 - Journal of Symbolic Logic 57 (2):677-681.
  • Learning via queries in [ +, < ].William I. Gasarch, Mark G. Pleszkoch & Robert Solovay - 1992 - Journal of Symbolic Logic 57 (1):53-81.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Inductive inference and unsolvability.Leonard M. Adleman & M. Blum - 1991 - Journal of Symbolic Logic 56 (3):891-900.
    It is shown that many different problems have the same degree of unsolvability. Among these problems are: THE INDUCTIVE INFERENCE PROBLEM. Infer in the limit an index for a recursive function f presented as f(0), f(1), f(2),.... THE RECURSIVE INDEX PROBLEM. Decide in the limit if i is the index of a total recursive function. THE ZERO NONVARIANT PROBLEM. Decide in the limit if a recursive function f presented as f(0), f(1), f(2),... has value unequal to zero for infinitely many (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Inductive Inference and Unsolvability.Leonard M. Adleman & M. Blum - 1991 - Journal of Symbolic Logic 56 (3):891-900.