Abstract 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.

A set A is autoreducible if one can compute, for all x, the value $A(x)$ by querying A only at places $y \neq x$. Furthermore, A is infinitely‐often autoreducible if, for infinitely many x, the value $A(x)$ can be computed by querying A only at places $y \neq x$. For all other x, the computation outputs a special symbol to signal that the reduction is undefined. It is shown that for polynomial time Turing and truth‐table autoreducibility there are A, B, C in the class EXP of all exponential‐time computable sets such that A is not infinitely‐often Turing autoreducible, B is Turing autoreducible but not infinitely‐often truth‐table autoreducible and C is truth‐table autoreducible with $g(n)+1$ queries but not infinitely‐often Turing autoreducible with $g(n)$ queries. Here n is the length of the input, g is nondecreasing, and there exists a polynomial p such that $p(n)$ bounds both the computation time and the value of g at input of length n. Furthermore, connections between notions of infinitely‐often autoreducibility and notions of approximability are investigated. The Hausdorff‐dimension of the class of sets which are not infinitely‐often autoreducible is shown to be 1.

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a $(\frac{1}{2}+o(1)){n \choose 2} $ upper bound and a nearly matching $0.32{n \choose 2}$ lower bound for the minimum possible number of queries. In contrast, if we allow randomness, then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

We consider the question whether there exists a set A such that every set polynomial-time Turing equivalent to A is also many-one equivalent to A. We show that if E=NE then no sparse set has this property. We give the first relativized world where there exists a set with this property, and in this world the set A is sparse.

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic nonadaptive setting, we prove a ( 1/2 +o(1))(n/2) upper bound and a nearly matching 0.32(n/2) lower bound for the minimum possible number of queries. In contrast, if we allow randomness then we obtain (by a randomized, nonadaptive algorithm) a much lower O(n log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

We use a Ramsey-theoretic argument to obtain the first lower bounds for approximations over Z/sub m/ by nonlinear polynomials: (i) A degree-2 polynomial over Z/sub m/ (m odd) must differ from the parity function on at least a 1/2-1/2((log n)/sup /spl Omega/(1)/) fraction of all points in the Boolean n-cube. A degree-O(1) polynomial over Z/sub m/ (m odd) must differ from the parity function on at least a 1/2-o(1) fraction of all points in the Boolean n-cube. These nonapproximability results imply the first known lower bounds on the top fanin of MAJoMOD/sub m/oAND/sub O(1)/ circuits (i.e., circuits with a single majority-gate at the output node, MOD/sub m/-gates at the middle level, and constant-fanin AND-gates at the input level) that compute parity: (i) MAJoMOD/sub m/oAND/sub 2/ circuits that compute parity must have top fanin 2((log n)/sup /spl Omega/(1)/). (ii) Parity cannot be computed by MAJoMODmoAND/sub O(1)/ circuits with top fanin O(1). Similar results hold for the MOD/sub q/ function as well.

Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and effort required to sequence the DNA in the missing gaps. This procedure has been used in a number of microbial sequencing projects including Streptococcus pneumoniae and other bacteria. In this paper we describe a theoretical framework for this problem and propose an improved method that guarantees to minimize the number of steps involved in the gap closure procedures. In given particular collection of n/2 DNA fragments we describe a strategy that requires. 0.75 log n work in eight parallel rounds of experiment closely matching a corresponding lower bound 0.5 log of n

Abstract 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: and, for m > 2, where #nA. (x1….. xn) = A(x1) + A(xn)(We identify with , where χA is the characteristic function of A.) If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODDnA and MODmnA: • ODDnA can be decided with n parallel queries to A, but not with n − 1. • ODDnA can be decided with ⌈log(n + 1)⌉ sequential queries to A but not with ⌈log(n + 1)⌉ − 1. • MODmnA can be decided with ⌈n/m⌉ + ⌊n/m⌋ parallel queries to A but not with ⌈n/m⌉ + ⌊n/m⌋ − 1. • MODmnA can be decided with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ sequential queries to A but not with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ − 1. The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.) In particular, every nonzero truth-table degree contains a set A such that ODDnA cannot be decided with n − 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODDnB can be decided with one query to B, a set's query complexity depends more on its structure than on its degree. For a fixed set A, Q(n, A) = {S: S can be decided with n sequential queries to A}. Q∥ (n, A) = {S : S can be decided with n parallel queries to A}. We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: • Q(0,A) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ … Q∥ (0, A) ⊂ Q∥ (1, A) ⊂ Q∥ (2, A) ⊂ … The same is true if A is a jump.

Motivated by the question of the relative complexities of the graph isomorphism and the graph automorphism problems, we define and study the modular graph automorphism problems. These are the decision problems mod k -GA which consist, for each k > 1, of deciding whether the number of automorphisms of a graph is divisible by k. The mod k -GA problems all turn out to be intermediate in difficulty between graph automorphism and graph isomorphism. We define an appropriate search problem corresponding to mod k -GA and design an algorithm that polynomial-time reduces the mod k -GA search problem to the decision problem. Combining this algorithm with an IP protocol, we obtain a randomized polynomial-time checker for mod$_{k}$-GA $\forall k>1$.

Prior results show that most bounded query hierarchies cannot contain finite gaps. For example, it is known that P/sub (m+1)-tt//sup SAT/=P/sub m-tt//sup SAT//spl rArr/P/sub btt//sup SAT/=P/sub m-tt//sup SAT/ and for all sets A/spl middot/FP/sub (m=1)-tt//sup A/=FP/sub m-tt//sup A//spl rArr/FP/sub btt//sup A/=FP/sub m-tt//sup A//spl middot/P/sub (m+1)-T//sup A/=P/sub m-T//sup A/=P/sub bT//sup A//spl middot/FP/sub (m+1)-T//sup A/=FP/sub m-T//sup A//spl rArr/FP/sub bT//sup A/=FP/sub m-T//sup A/ where P/sub m-tt//sup A/ is the set of languages computable by polynomial-time Turing machines that make m nonadaptive queries to A; P/sub btt//sup A/=/spl cup//sub m/P/sub m-tt//sup A/, P/sub m-t//sup A/ and P/sub bT//sup A/ are the analogous adaptive queries classes; and FP/sub m-tt//sup A/, FP/sub btt//sup A/, FP/sub m-T//sup A/, and FP/sub bT//sup A/ in turn are the analogous function classes. It was widely expected that these general results would extend to the remaining case-languages computed with nonadaptive queries-yet results remained elusive. The best known was that P/sub 2m-tt//sup A/=P/sub m-tt//sup A//spl rArr/P/sub btt//sup A/=P/sub m-tt//sup A/. We disprove the conjecture, in fact, P/sub [4/3m]-tt//sup A/=P/sub m-tt//sup A/not/spl rArr/P/sub ([4/3m]+1)-tt/=P/sub [4/3m]-tt//sup A/. Thus there is a P/sub m-tt//sup A/ hierarchy that contains a finite gap. We also make progress on the 3-tt vs. 2-tt case: P/sub 3-tt//sup A/=P/sub 2-tt//sup A//spl rArr/P/sub btt//sup A//spl sube/P/sub 2-tt//sup A//poly.

Since the publication of M. Furst et al. (1984) seminal paper connecting AC/sup 0/ with the polynomial hierarchy, it has been well known that circuit lower bounds allow you to construct oracles that separate complexity classes. We show that similar circuit lower bounds allow you to construct oracles that collapse complexity classes. For example, based on Hastad's parity lower bound, we construct an oracle such that P=PH/spl sub//spl oplus/P=EXP.

We survey the theoretical use of DNA computing to solve intractable problems. We also discuss the relationship between problems in DNA computing and questions in complexity theory.

Theorem 1.3There exists a relativized world where we can detect unique solutions for NP problems yet P # NP.

Article One help-bit doesn't help Share on Authors: Richard Beigel Lehigh University, Elect Eng Comp Science, 19 Memorial Dr W Ste 2, Bethlehem PA Lehigh University, Elect Eng Comp Science, 19 Memorial Dr W Ste 2, Bethlehem PAView Profile , Tirza Hirst Bar-llan University, Department of Mathematics and Computer Science, Bar-Ilan University, 52900 Ramat-Gan, Israel Bar-llan University, Department of Mathematics and Computer Science, Bar-Ilan University, 52900 Ramat-Gan, IsraelView Profile Authors Info & Claims STOC '98: Proceedings of the thirtieth annual ACM symposium on Theory of computingMay 1998 Pages 124–130https://doi.org/10.1145/276698.276720Online:23 May 1998Publication History 6citation229DownloadsMetricsTotal Citations6Total Downloads229Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The $\beta$ hierarchy consists of classes $\beta_k={\rm NP}[log kn ]\subseteq {\rm NP}$. Unlike collapses in the polynomial hierarchy and the Boolean hierarchy, collapses in the $\beta$ hierarchy do not seem to translate up, nor does closure under complement seem to cause the hierarchy to collapse. For any consistent set of collapses and separations of levels of the hierarchy that respects ${\rm P} = \beta_1\subseteq \beta_2\subseteq \cdots \subseteq {\rm NP}$, we can construct an oracle relative to which those collapses and separations hold; at the same time we can make distinct levels of the hierarchy closed under computation or not, as we wish. To give two relatively tame examples: for any $k \geq 1$, we construct an oracle relative to which \[ {\rm P} = \beta_{k} \neq \beta_{k+1} \neq \beta_{k+2} \neq \cdots \] and another oracle relative to which \[ {\rm P} = \beta_{k} \neq \beta_{k+1} = {\rm PSPACE}. \] We also construct an oracle relative to which $\beta_{2k} = \beta_{2k+1} \neq \beta_{2k+2}$ for all k.

We demonstrate the use of Kolmogorov complexity in average case analysis of algorithms through a classical example: adding two n-bit numbers in [log2 n] + 2 steps on average. We simplify the analysis of Burks et al. (1961) and (in more complete forms) Briley (1973) and Schay (1995).

C.B. Wilson's (1985) model of oracle gates provides a framework for considering reductions whose strength is intermediate between truth-table and Turing. Improving on a stream of results by previous authors, we prove that PL and PP are closed under NC/sub 1/ reductions. This answers an open problem of M. Ogihara (1996). More generally, we show that NC/sub k+1//sup PP/=AC/sub k//sup PP/ and NC/sub k+1//sup PL/=AC/sub k//sup PL/ for all k/spl ges/0. On the other hand, we construct an oracle A such that NC/sub k/(PP/sup A/)/spl ne/NC/sub k+1/(PP/sup A/) for all integers k/spl ges/1. Slightly weaker than NC/sub 1/ reductions are Boolean formula reductions. We ask whether PL and PP are closed under Boolean formula reductions. This is a nontrivial question despite NC/sub 1/=BF, because that equality is easily seen not to relativize. We prove that P/sub log2n/loglogn-T//sup PP//spl sube/BF/sup PP//spl sube/PrTIME(n/sup O(logn)/). Because P/sub log2n/loglogn-T//sup PP//spl nsub/PP relative to an oracle, we think it is unlikely that PP is closed under Boolean formula reductions. We also show that PL is unlikely to be closed under BF reductions.

We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MOD/sub m/ gates at level one. We show that the fan-in of the AND gates can be reduced to O(log n) in the case where m is unbounded, and to a constant in the case where m is constant. We then use these upper bounds to derive exponential lower bounds for this class of circuits. In the unbounded m case, this yields a new proof of a lower bound of Grolmusz; in the constant m case, our result sharpens his lower bound. In addition, we prove an exponential lower bound if OR gates are also permitted on level two and m is a constant prime power.

There have been several papers over the last ten years that consider the number of queries needed to compute a function as a measure of its complexity. The following function has been studied extensively in that light: FaA(x1,…,xa) = A(x1)…A(xa). We are interested in the complexity (in terms of the number of queries) of approximating FaA. Let b ⩽ a and let f be any function such that FaA(x1,…,xa) and f(x1,…,xa) agree on at least b bits. For a general set A we have matching upper and lower bounds on f that depend on coding theory. These are applied to get exact bounds for the case where A is semirecursive, A is superterse, and (assuming P ≠ NP) A = SAT. We obtain exact bounds when A is the halting problem using different methods.

We consider worst case time bounds for NP-complete problems including 3-coloring, 3-edge-coloring, and 3-list-coloring. Our algorithms are based on a common generalization of these problems, called symbol-system satisfiability or, briefly, SSS. 3-SAT is equivalent to (2,3)-SSS while the other problems above are special cases of (3,2)-SSS; there is also a natural duality transformation from (a,b)-SSS to (b,a)-SSS. We give a fast algorithm for (3,2)-SSS and use it to improve the time bounds for solving the other problems listed above.

Consider a set of n processors that can communicate with each other. Assume that each processor can be either "good" or "faulty". Also assume that the processors can test each other. We consider how to use parallel testing rounds to identify the faulty processors, given an upper bound t on their number. We prove that 4 rounds are necessary and sufficient when 2/spl radic/(2n)/spl les/0.03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t/spl ges/0.49n (for n sufficiently large), and 10 rounds are sufficient when t<0.5n (for all n). (It is well known that no general solution is possible when t/spl ges/0.5n).

We study the fine structure of the classification of sets of natural numbers A according to the number of queries which are needed to compute the n-fold characteristic function of A. A complete characterization is obtained, relating the question to finite combinatorics. In order to obtain an explicit description we consider several interesting combinatorial problems.

Much structural work on NP-complete sets has exploited SAT′s d-self-reducibility. In this paper, we exploit the additional fact that SAT is a d-cylinder to show that NP-complete sets are p-superterse unless P = NP. In fact, every set that is NP-hard under polynomial-time no(1)-tt reductions is p-superterse unless P = NP. In particular, no p-selective set is NP-hard under polynomial-time no(1)-tt reductions unless P = NP. In addition, no easily countable set is NP-hard under Turing reductions unless P = NP. Self-reducibility does not seem to suffice far our main result: in a relativized world, we construct a d-self-reducible set in NP − P that is polynomial-time 2-tt reducible to a p-selective set.

In this seminal paper on probabilistic Turing machines, Gill asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming P ≠ PP) separation of certain query hierarchies over PP. Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons) and a lower bound on the number of threshold gates that are needed to compute the parity function.

Consider a set of processors, V, that can communicate with each other.Assume that each processor can be either "good" or "faulty".Also assume that the processors can be used to test each other.We provide a parallel algorithm that determines which processors are good and which are faulty in 32 rounds of testing, pre Tided that a strict majority of the processors are good.

Define the MOD~-degree of a boolean function F to be the smallest degree of any polynomial P, over the ring of integers modulo m, such that for all O-1 assignments 5, F(o?) = O iff P(~= O.We obtain the unexpected result that the MOD,r,-degree of the OR of N variables is 0(~), where r is the number of distinct prime factors of m.This is optimal in the case of representation by symmetric polynomials.The MOD,, function is O if the number of input ones is a multiple of n and is 1 otherwise.We show that the MOD~-degree of both the MOD. and lMODn functions is N$)(l) exactly when there is a prime dividing n but not m.The MOD~-degree of the MOD~function is 1;we show that the MODrn,-degree of lMODm is NtiflJ if m is not a power of a prime, O(1) otherwise.A corollary is that there exists an oracle relative to which the MODm P classes (such as @P) have this structure: MODm P is closed under complement and union iff m is a prime power, and MOD.P is a subset of MODmP iff all primes dividing n also divide m.

Suppose that f is computed by a constant depth circuit with 2m AND-, OR-, and NOT-gates, and m majority-gates. We prove that f is computed by a constant depth circuit with 2mo(1) AND-, OR-, and NOT-gates, and a single majority-gate, which is at the root.

A basic question about NP is whether or not search reduces in polynomial time to decision. We indicate that the answer is negative: under a complexity assumption (that deterministic and nondeterministic doubleexponential time are unequal) we construct a language in NP for which search does not reduce to decision. These ideas extend in a natural way to interactive proofs and program checking. Under similar assumptions we present languages in NP for which it is harder to prove membership interactively than it is to decide this membership. Similarly we present languages where checking is harder than computing membership. Each of the following properties --- checkability, random-self-reducibility, reduction from search to decision, and interactive proofs in which the prover's power is limited to deciding membership in the language itself --- implies coherence, one of the weakest forms of self-reducibility. Under assumptions about triple-exponential time, we construct incoherent sets in NP....

It has been shown by A. Yao (1990) that every language in ACC is recognized by a sequence of depth-2 probabilistic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog (n) at the leaves. The authors simplify Yao's proof and strengthen his results: every language in ACC is recognized by a sequence of depth-2 deterministic circuits with a symmetric gate at the root and n/sup polylog/(n) AND gates of fan-in polylog(n) at the leaves. They also analyze and improve modulus-amplifying polynomials constructed by S. Toda (1989) and Yao: this yields smaller circuits in Yao's and the present results on ACC.>

We consider the problem of approximating a Boolean function f : f0; 1g n ! f0; 1g by the sign of an integer polynomial p of degree k. For us, a polynomial p(x) predicts the value of f(x) if, whenever p(x) 0, f(x) = 1, and whenever p(x) ! 0, f(x) = 0. A low-degree polynomial p is a good approximator for f if it predicts f at almost all points. Given a positive integer k, and a Boolean function f , we ask, "how good is the best degree k approximation to f?" We introduce a new lower bound technique which applies to any Boolean function. We show that the lower bound technique yields tight bounds in the case f is parity. Minsky and Papert [10] proved that a perceptron can not compute parity; our bounds indicate exactly how well Yale University, Dept. of Computer Science, P.O. Box 208285, New Haven CT 06520-8285. y Email: [email protected]. z Email: [email protected]. Supported in part by NSF grants CCR-8808949 and CCR-8958528. x Carnegie-Mellon University, Schoo...

In his seminal paper on probabilistic Turing machines, Gill [13] asked whether the class PP is closed under intersection and union. We give a positive answer to this question. We also show that PP is closed under a variety of polynomial-time truth-table reductions. Consequences in complexity theory include the definite collapse and (assuming P 6= PP) separation of certain query hierarchies over PP. Similar techniques allow us to combine several threshold gates into a single threshold gate. Consequences in the study of circuits include the simulation of circuits with a small number of threshold gates by circuits having only a single threshold gate at the root (perceptrons), and a lower bound on the number of threshold gates needed to compute the parity function. 1. Introduction The class PP was defined in 1972 by John Gill [13, 14] and independently by Janos Simon [26] in 1974. PP is the class of languages accepted by a polynomial-time bounded nondeterministic Turing machine t...

We examine the problem of coloring a subgraph of a k-colorable graph without knowing the entire graph. Our results are phrased in terms of a game with two players: (a) the Mapmaker, who must color a fixed set X of vertices in a manner extendible to a k-coloring of the entire graph, and (b) the Explorer, who adds vertices and edges to the graph, hoping to force the Mapmaker to change his mind many times about how to color X. We show that if k ≥ 3, then the Explorer can force an exponential number of mind-changes; but if k = 2, then she can only force a linear number of mind-changes. Applications to recursive graph theory are given.

We show that probabilistic polynomial time (PP) is closed under polynomial-time parity reductions. As corollaries, we show that several complexity classes are contained in PP.

Well-known complexity classes such as NP, co-NP, ⊕P (PARITY-P), and PP are produced by considering a nondeterministic polynomial time Turing machine N and defining acceptance in terms of the number of accepting paths in N. That is, they are subclasses of P#P[1]. Other interesting classes such as MODk P and C + P are also subclasses of P#P[1]. Many relations among these classes are unresolved. Of course, these classes coincide if P = PSPACE. However, we develop a simple combinatorial technique for constructing oracles that separate counting classes. Our results suggest that it will be difficult to resolve the unknown relationships among different counting classes. In addition to presenting new oracle separations, we simplify several previous constructions.

The unbounded search problem was posed by Bentley and Yao. It is the problem of finding a key in a linearly ordered unbounded table, with the proviso that the number of comparisons is to be minimized. It is shown that Bentley and Yao’s lower bound is essentially optimal, and some new upper bounds for the unbounded search problem are proven. The solution of this problem in parallel is demon-strated.

A k-sorter is a device that sorts k objects in unit time. The complexity of an algorithm that uses a k-sorter is defined as the number of applications of the k-sorter. In this measure, the complexity of sorting n objects is between n log n/k log k and 4n log n/k log k, up to first-order terms in n and k.>

An oracle A is k-cheatable if there is a polynomial-time algorithm to determine the answers to 2k parallel queries to A from the answers to only k queries to some other oracle B. It is known that 1-cheatable sets cannot be bi-immune for P. In contrast, we construct 2-cheatable sets that are bi-immune for arbitrary time complexity classes. In addition, for each k, we construct a set that is (k + 1)-cheatable, but not k-cheatable; we show that this separation does not hold with bi-immunity. We show that if a recursive set A is bi-immune for P then there exists a nontrivial 1-cheatable set that is polynomial-time m-reducible to A. Consequently if NP contains a set that is bi-immune for P then NP contains a set that is not polynomial-time Turing-equivalent to a self-reducible set.

Consider a system of processing elements in which elements may administer tests to other elements. We show, surprisingly, that a constant number of rounds of parallel testing are sufficient to identify all faults (in all cases where fault identification is possible). We also present an O(log log n=t t) algorithm with a small constant of proportionality, where n denotes the total number of processors and t denotes the number of faulty processors. Both of these results improve upon the previous best, which was O(log n=t t) rounds. For the problems of identifying a single faulty processor (diagnosis-with-repair) and identifying a single good processor, we present an oblivious constant-time algorithm using a fixed 3-regular interconnect that tolerates a linear number of faults. This contrasts with the well-known result that every oblivious algorithm for complete diagnosis must use a number of rounds that is linear in t. 1 Introduction Consider a system composed of many processing element...

A recursive graph is a graph whose edge set and vertex set are both recursive. Although the chromatic number of a recursive graph G (denoted #(G)) cannot be determined recursively, it can be determined if queries to the halting set are allowed. We show that the problem of determining the chromatic number of a recursive graph with a minimum number of queries to the halting set, is closely related to the unbounded search problem. In particular if f is a non-decreasing function such that P i#0 2 -f(i) is effectively computable, then there is an algorithm to determine #(G) with f(#(G)) queries to K i# P i#0 2 -f(i) # 1 (i.e., f satisfies Kraft's inequality). We also investigate recursive chromatic numbers (which require queries to a set much harder than the halting set, namely # ### ), the effect of allowing queries to a weaker set, and the effect of being able to ask p queries at a time. Most of our results are also true for highly recursive graphs (graphs where one can determine t...

A query-bounded Turing machine is an oracle machine which computes its output function from a bounded number of queries to its oracle. In this paper we investigate the behavior of nondeterministic query-bounded Turing machines. In particular we study how easily such machines can compute the function F A n (x 1 , . . . , x n ) from A, where A # N and F A n (x 1 , . . . , x n ) = ##A (x 1 ), . . . , #A (x n )#. We show that each truth-table degree contains a set A such that, F A n can be nondeterministically computed from A by asking at most one question per nondeterministic branch; and that every set of the form A # also has this property. On the other hand, we show that if A is a 1-generic set then F A n cannot be nondeterministically computed from A in less that n queries to A; and that each non-zero r.e. Turing degree contains an r.e. set A with the same property. If the machines involved can only make queries that are part of their input then all sets such that F A n ca...