Nondeterministic bounded query reducibilities (Q1120564)

The behavior of nondeterministic oracle machines with a bounded number of calls to the oracle is considered. For any set A of natural numbers we define \(F^ A_ n(x_ 1,...,x_ n)=<\chi_ A(x_ 1),...,\chi_ A(x_ n)>\). Denote by FQ(n,B) (NFQ(n,B)) the class of functions computable by a deterministic (nondeterministic) machine with the oracle B and with at most n calls to B for each (branch of its) computation. A set a is called n-subjective if \(F^ A_ m\in NFQ(n,A)\) for all \(m\in N\); it is called objective if, for all \(n>0\), \(F^ A_ n\not\in NFQ(n- 1,A).\) In the paper the authors give a series of interesting results on the classes NFQ(n,A), some of them are the following: 1) Each truth-table degree contains a 1-subjective set. 2) If A is any set, then A' is 1- subjective. 3) There exist 1-subjective sets A such that for all n and all sets X, \(F^ A_ n\) is not in \(FQ(n-1,X);\) 4) If A is 1-generic, then a is objective; 5) Each non-zero r.e. Turing degree contains an r.e. objective set.