Complexity-Restricted Advice Functions.
The authors consider uniform subclasses of the nonuniform  complexity classes defined by Karp and Lipton [L'Enseign. Math., 28 (1982)] via the notion of advice functions. These  subclasses are obtained by restricting the complexity of  computing correct advice.  Also, the effect of allowing  advice functions of limited complexity to depend on the  input rather than on the input's length is investigated.  Among other results, using the notions described above,  new characterizations of (a) $NP^{NP\cap SPARSE}$, (b) $\NP$ with  a restricted access to an $\NP$ oracle, and (c) the odd  levels of the boolean hierarchy are given.  As a consequence, it is shown that every set that is nondeterministically truth-table reducible to SAT in the  sense of Rich [J. Comput. System Sci., 38 (1989),  pp. 511--523] is already deterministically truth-table reducible  to SAT. Furthermore, it turns out that the $\NP$  reduction classes of bounded versions of this reducibility  coincide with the odd levels of the boolean hierarchy.
Introduction
. In their fundamental paper, Karp and Lipton [23] introduced
the notion of advice functions and investigated nonuniform complexity classes
which they denoted by C=F , where C is a class of sets and F is a class of (advice)
functions. A typical class is P=poly, where poly is the set of polynomially length
bounded functions. The interest in P=poly stems from the fact that it consists
exactly of the languages that can be computed by polynomially size-bounded circuits
[34].
Intuitively, a set A is in C=F , if A can be solved by a machine of type C
that gets, in addition to the input x, the advice f(x), where f is a function in F
depending only on the length of x. Many researchers have considered nonuniform
classes where the function class F is defined by a quantitative length restriction
such as poly and log (see, for example, [3, 5, 23, 36]). Note that for such F there are
nonrecursive functions in F , and therefore C=F contains nonrecursive languages.
Here, we consider uniform language classes obtained by imposing complexity
bounds on the advice functions. Note that K-amper [22] investigates refinements of
the original C=F definition by delimiting the complexity of proof sets, i.e., special
Abteilung f?r Theoretische Informatik, Universit?t Ulm, Oberer Eselsberg, D-W-7900 Ulm,
Germany. Supported in part by the DAAD through Acciones Integradas 1991, 313-AI-e-es/zk.
y Abteilung f?r Theoretische Informatik, Universit?t Ulm, Oberer Eselsberg, D-W-7900 Ulm,
Germany. Work done in part while visiting the University of Rochester. Supported in part by DFG
Postdoctoral Stipend Th 472/1-1, NSF Grant CCR-8957604, and by the DAAD through Acciones
Integradas 1991, 313-AI-e-es/zk.
sets of correct advice. In contrast to this, we directly bound the complexity of
computing correct advice. With this concept, we are able to show characterizations
as well as finer distinctions of several complexity classes. For example, we show
that the class NP NP"SPARSE coincides with the class NP=OptP[O(log n)], a subclass
of NP= log, where correct advice is computable by an OptP function [29], i.e.,
One can interpret equality (1.1) as stating that (exactly) the languages in
NP NP"SPARSE can be computed in the following way: on input x of length n, at
first an OptP[O(log n)] precomputation takes place that gets as input only 1 n .
The (logarithmically length-bounded) output of this precomputation is then passed
along with x to the subsequent NP computation, that decides the membership
of x.
Motivated by the relativized separation of P and NP of Baker, Gill, and Solovay
[2] (exploiting the fact that an NP oracle machine can ask superpolynomially
many queries), Book, Long, and Selman [11] introduced restricted relativizations
of NP by bounding the number of oracle queries in various ways. Subsequently,
Long [32] investigated the relationship between restricted access of nondeterministic
machines to an oracle and full access to a sparse oracle set. Let NP A
R be the
class of all languages whose membership in NP A is witnessed by an oracle machine
such that the number of potential oracle queries in A (asked on some oracle) is
polynomially bounded. From this definition, it is clear that NP NP"SPARSE is contained
in NP NP
R . Since also coNP is contained in NP NP
R , NP NP"SPARSE and NP NP
R are
different unless the polynomial hierarchy collapses [21]. By considering the proof of
equality (1.1), we will see that if we let the OptP[O(log n)] advice function depend
not only on the length of the input but on the input itself, we get a characterization
of NP NP
R . This leads us to define the class C==F , that is defined in the same way as
C=F , but with the advice functions depending on the input. Thus, we obtain the
following characterization of NP NP
R ,
The characterizations (1.1) and (1.2) give insight into the difference between restricted
access to NP oracles and full access to sparse NP sets.
It seems that the notion of C==F is an appropriate concept for studying different
kinds of truth-table reducibilities. Let - SAT
k be the k-ary characteristic function of
SAT. Then, P==- SAT
k ffiFP is the class of sets that are k-truth-table reducible to some
NP set. It is known that these classes are interleaved with levels of the boolean
hierarchy:
is closed under complementation, these classes are all different unless the boolean
hierarchy collapses.
is the class of sets that are k-truth-table reducible to some NP
set, where the evaluator is an NP machine. These classes turn out to coincide with
the odd levels of the boolean hierarchy, giving for the first time a charcterization
of the levels of the boolean hierarchy in terms of reduction classes,
Furthermore, we show that NP(2k
k-tt , where NP NP
k-tt is the class
of sets that are nondeterministically k-truth-table reducible to a set in NP in the
sense of [35] 1 , whereas in the unbounded case all sets nondeterministically truth-table
reducible to SAT are already deterministically truth-table reducible to SAT,
i.e., NP NP
tt . The latter result also holds for the strong nondeterministic
truth-table reducibility - SN
tt introduced by Long [31], i.e., we show that fA j A - SN
SATg.
The paper is organized as follows. Section 2 introduces notation and gives
basic definitions. In Section 3, we prove the above mentioned characterizations
of NP NP"SPARSE and NP NP
R and we show that changing from OptP[O(log n)]
to the larger function class FewOptP (containing all functions whose membership
in OptP is witnessed by an NP transducer that generates only polynomially
many different outputs) does not increase the power of NP=OptP[O(log n)] and
NP==OptP[O(log n)].
In Section 4, we separate some of these complexity classes in relativized world;
the main result is a separation of P=OptP[O(log n)] and P NP"SPARSE[O(logn)] .
In Section 5, we give several characterizations of certain levels of the boolean
hierarchy in terms of various complexity restricted advice function classes.
2. Preliminaries and Notation. All languages considered here are over the
alphabet 1g. For a string x 2 \Sigma   ; jxj denotes its length. We assume the existence
of a pairing function h\Delta; \Deltai : \Sigma   \Theta \Sigma   ! \Sigma   that is computable in polynomial
time and has inverses also computable in polynomial time. h\Delta; \Deltai can be extended to
encode finite sequences strings into a string hx . For a
set A, jAj denotes its cardinality. The complement \Sigma   \Gamma A of A is denoted by A.
A -n is the set of all strings in A of length less than or equal to n.
A languages S is sparse, if there is a polynomial p such that for all n, the
number of words in S up to length n is at most p(n). Let SPARSE be the class
of all sparse languages. A set T is tally, if T is a subset of 1   . Let TALLY be the
class of all tally sets.
We assume that the reader is familiar with (nondeterministic, polynomial-time
bounded, oracle) Turing machines and complexity classes (see [4, 36]). FP is the
class of functions computable by a deterministic polynomial-time bounded Turing
transducer. An NP transducer is a nondeterministic polynomial-time bounded
Turing machine T that on every branch either accepts and writes a binary number
1 By requiring the NP generator to be single valued, Rich [35] has modified the nondeterministic
truth-table reducibility originally defined by Ladner, Lynch, and Selman [30].
on its output tape or rejects. The set of outputs generated by T on input x is
denoted by out T (x).
Krentel [29] defines an NP metric Turing machine to be an NP transducer
that accepts on every branch. For an NP metric Turing machine T and an input
be the maximum [minimum] output generated by T
on input x on any accepting computation of T . The class OptP [29] of optimization
functions is defined as
is an NP metric Turing machine g:
For a class R of functions on the natural numbers (called restricting functions), we
define the subclass
containing all optimization functions f 2 OptP such that the length of f(x) in
binary is bounded in jxj by a function from R.
denotes the class of sets whose membership in P NP can be witnessed by
an oracle machine M making for some r 2 R at most r(n) many queries on inputs
of length n. In the case that R is a singleton set frg we simply write OptP[r] and
respectively. Throughout the paper we assume that for every restricting
function r the function x 7! r(jxj) is computable in polynomial time.
Karp and Lipton [23] introduced the notion of advice functions in order to
define nonuniform complexity classes. For a class C of sets and a class F of functions
from \Sigma   to \Sigma   let C=F be the class of sets A such that there is a set B 2 C and a
function h 2 F such that for all x 2 \Sigma
Note that the advice function h depends only on the length of x. By canceling this
restriction we obtain the class C==F of all sets A such that there is a set B 2 C and
a function h 2 F such that for all x 2 \Sigma
By definition, C=F is a subset of C==F for each class of sets C and each class of
functions F which fulfills the condition that if h 2 F , then also x 7! h(1 jxj
Special advice function classes considered in the literature are poly
there exists a polynomial p such that for all x, jh(x)j - p(jxj)g and log
O(log(jxj))g.
3. NP NP"SPARSE versus NP NP
R . In this section we show that NP NP"SPARSE can
be characterized as the class NP=OptP[O(log n)], i.e., the class of sets that are
accepted by an NP machine with advice of a logarithmically length bounded OptP
function. Further, it turns out that the related class NP NP
R (see definition below)
coincides with NP==OptP[O(log n)]. For the latter two classes we can show that
they are also equal to P==OptP[O(log n)] which, by a result of Krentel [29], is
identical to P NP[O(logn)] .
Definition 3.1. [11] For any oracle Turing machine M and any string
be the set of all oracle queries that M may ask on input x
using oracle A, i.e., the set of all strings y 2 \Sigma   such that in some computation of
M on input x under oracle A the oracle is queried about y. Q(M;x) is the set of all
oracle queries of M on input x using any oracle, i.e.,
A'\Sigma   Q(M; A; x).
For any set A, NPR (A) is the class of sets L 2 NP(A) whose membership is
witnessed by a machine M such that the number of potential oracle queries in A is
polynomially bounded, i.e., there exists a polynomial p such that jQ(M;x) " Aj -
p(jxj) for all x.
Our first theorem states that if a language L is accepted by an NP oracle
machine M using an NP oracle A in such a way that the number of potential oracle
queries that are in A is polynomially bounded, then L is in NP==OptP[O(log n)],
i.e., membership to L can be tested by an NP machine which gets along with the
input the precomputed value of an OptP[O(log n)] function. In the special case that
A is sparse this containment can be strengthened to NP=OptP[O(log n)], i.e., for
all inputs of the same length the advice function yields the same result. The proof
is by a census argument similar to that used by Hemachandra [18] and Kadin [21].
Theorem 3.2.
Proof. Let for an NP machine M and an oracle A in NP, and let
p be a polynomial that bounds the running time of M .
To show i) let r be a polynomial such that jQ(M;x) " Aj - r(jxj) for all x. An
NP machine knowing the size of the set Q(M;x) " A can guess this set (note that
the problem to decide for given strings x and y whether y is in Q(M;x) " A is in
NP). Define the function
and the set
since h(x) is the maximum output of the
following algorithm.
On input x guess k - r(jxj) and x
it holds for all x 2 \Sigma   that x 2 L if and only if hx; h(x)i 2 B. Therefore, L
is in NP==OptP[O(log n)]:
For ii) let A be sparse and r be a polynomial such that jA -p(n) j - r(n), for
all n. Define the function
and the set
By a similar argument as in the proof of i), x 2 L if and only if hx; h(1 jxj
This shows that L is in NP=OptP[O(log n)].
Combining Theorem 3.2 ii) with the result of Balc'azar and Sch-oning [5] that
it follows that for every conp set in
NP=log correct advice can already be computed by an OptP function.
Corollary 3.3. NP=log "
To show the reverse containments of Theorem 3.2, we make use of the following
lemma. It states that every OptP function h can be computed by a deterministic
polynomial-time oracle machine by asking jh(x)j many queries to an NP oracle.
Lemma 3.4. [29] OptP[r] ' FP NP[r] for any restricting function r.
Corollary 3.5.
Proof. By Theorem 3.2, it only remains to show the inclusions from right to
left.
To show i), let L be in NP==OptP[O(log n)] via an NP machine N and an
optimization function h. Then L can be accepted by an NP machine M that
computes deterministically by binary search the value of h according to Lemma 3.4
asking O(log n) many queries to an NP oracle, and then simulates N without asking
further oracle queries. Since Q(M;x) is polynomially bounded, it follows that L is
in NP NP
R .
If h is a function that depends only on the length of its argument, then h(x)
can be computed by binary search using the tally NP set )g.
This proves ii).
Note that the above proof shows that every language in NP==OptP[O(log n)]
(and thus in NP NP
R ) can in fact be accepted by an NP oracle machine M such that
Q(M;x) is polynomially bounded.
In the next lemma, we show that an NP computation getting along with the
input the result h(x) of an OptP precomputation can be transformed into a P computation
by precomputing one additional bit. Note that this bit actually depends
on x even if h(x) only depends on the length of x.
Lemma 3.6. NP==OptP[r] ' P==OptP[r + 1], for any function r.
Proof. Let L be in NP==OptP[r], witnessed by an NP set B and an OptP[r]
function . Define the OptP[r+1] function
h(x)0; otherwise.
Then it holds for all x that hx; where the set
is oddg is in P. The case that can be proved analogously.
Combining Corollary 3.5 i) and Lemma 3.6 we obtain a further characterization
of the class NP NP
R and its closure under complementation. Note that
Corollary 3.7. NP NP
Corollary 3.8. NP NP
R is closed under complementation.
Remark 3.9. The results stated in Corollary 3.5 can be extended to the classes
of the polynomial-time hierarchy [37]. In order to do so, we define restricted
relativizations of the \Sigma-levels of the polynomial hierarchy. \Sigma C
k;R is the class of all
sets L accepted by a k-alternating polynomial-time Turing machine [16] using an
oracle A from C such that jQ(M;x) " Aj is polynomially bounded. Then, the results
stated in Corollary 3.5 can be extended to
where Opt C is the class of optimization functions computable by an NP transducer
using some oracle in the class C. Since \Sigma k =Opt \Sigma k\Gamma1 [O(log n)] is included in
sharpens the recent result in [13] that \Sigma \Sigma k "SPARSE
Remark 3.10. The advice (even depending on the input) provided by an
OptP[O(log n)] function does not increase the power of the probabilistic class
This follows from the result by Toda [40] that
since PP==OptP[O(log n)] coincides with the class PP==FP NP[O(logn)]
(see Lemma 3.4) that is clearly contained in PP NP
R .
Next, we consider uniform subclasses of P=log and P=poly. Whereas the
proof of Corollary 3.5 ii) also yields the inclusion of P=OptP[O(log n)] in
the census technique of Theorem 3.2 cannot be applied to obtain
the reverse containment. The next theorem is proved by constructing (long enough
initial segments of) a sparse NP set by an OptP computation. The underlying
technique was used by Mahaney [33] to show that NP NP"SPARSE ' P NP .
Theorem 3.11. P NP"SPARSE ' P=OptP:
Proof. Let machine M and a sparse NP set S. Let p
and r be polynomials such that p bounds the running time of M and jS -n j - r(n).
since h(x) is the maximum output of the following algorithm.
On input 1 n guess k - r(p(n)) and x
Now, the computation of M using oracle S on input x can be simulated by a P
machine answering oracle questions according to the set h(1 jxj ).
Let FewOptP be the class of functions f 2 OptP computed by an NP transducer
that produces at most a polynomial number of different outputs. Clearly,
OptP[O(log n)] ' FewOptP, and obviously, this is a proper inclusion.
However, as shown by the next theorem, the classes NP=OptP[O(log n)] and
NP==OptP[O(log n)] remain unchanged when the function class OptP[O(log n)] is
replaced by the larger class FewOptP.
Theorem 3.12.
Proof. Let L be a set in NP==FewOptP via A 2 NP and f 2 FewOptP. Let T
be an NP metric machine for f , i.e., (the proof for
and the number of different outputs of T is polynomially bounded. Define the
function
and the set
It is easy to see that h 2 OptP[O(log n)] and B 2 NP. Now, x is in L if and only if
hx; h(x)i is in B, and therefore, L is in NP==OptP[O(log
The latter equality follows from Corollaries 3.5, part i), and 3.7. The proof of ii)
is analogous, we only have to replace out T (x) by out T (1 jxj ).
The technique used in the previous proof cannot be applied to show that
the classes P=OptP[O(log n)] and P=FewOptP are equal. However, the proof of
P=OptP[O(log n)] ' P NP"SPARSE[O(logn)] (using binary search, see the proof of Corollary
3.5 ii)) can be refined to show the following theorem. It states that a set
in P=FewOptP can be decided in polynomial time by querying a sparse NP oracle
(polynomially often).
Theorem 3.13. P=FewOptP ' P NP"SPARSE .
Proof. Let f be in FewOptP and let T be an NP transducer computing f .
Using the sparse NP set
as oracle, f(x) can be computed in polynomial time by determining first jout T (1 n )j
and then applying a prefix search to find the optimum value in out T (1 n ).
The known relationships of the language classes considered in this section are
summarized in the diagram of Figure 3.1.
@
@
e
e
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi \Phi
\Phi \Phi \Phi \Phi \Phi
R
\Phi \Phi \Phi
\Phi \Phi \Phi
\Phi \Phi \Phi
\Phi \Phi \Phi
Fig. 3.1. Inclusion structure of some considered complexity classes; thick lines indicate that
there are relativized separations (see Section 4).
4. Relativized Separations. Since Baker, Gill, and Solovay [2] separated P
from NP relative to some oracle, relativizations have been an important subject in
complexity theory. In this section, we discuss which of the inclusions in Figure 3.1
are strict, at least in some relativized world.
Since there are nonrecursive sets in P=poly and in NP=poly, these two classes
are clearly different from all other (recursive) classes considered here. Whether
there are any other strict inclusions in the diagram of Figure 3.1 is not known.
For some of the inclusions, however, the question whether they are proper can be
linked to central open problems in complexity theory.
For example, by the result of Karp, Lipton, and Sipser (see [23]) that NP '
P=poly implies the collapse of the polynomial hierarchy to its second level, it follows
that if PH 6= \Sigma 2 , then NP is not contained in any of the classes on the left column
of

Figure

3.1. Since this holds in all relativized worlds, and since there exists an
oracle separating PH from \Sigma 2 [24], it follows that relative to this oracle all the
inclusions between the first and the second column are proper.
Similarly, using the result of Kadin [21] that conp ' NP NP"SPARSE implies
P NP[O(logn)] . Since, as it is easily seen, the inclusion conp ' NP=OptP implies
we can state the following theorem.
Theorem 4.1. PH 6= P NP ) NP=OptP 6= P==OptP.
Furthermore, by the recent result of Toda [39] that PH ' P PP , it follows that
Beigel [7] constructed an oracle A such that P NP A
separates P NP[O(logn)] and P NP (for a direct
proof see [14]).
Cai et al. [15] showed the existence of an oracle A such that relative to A the
boolean hierarchy is infinite, i.e., In fact, Cai et al.
construct the oracle A in such a way that, for all k, some tally test language
is in conp A Because it holds for every oracle set B that
[43, 28, 8], it follows that L
Since P=OptP[k] is contained in the 2 k -th level of the boolean hierarchy, this result
is optimal.
Clearly, if the boolean hierarchy is proper, it does not have complete sets.
Since the class P=OptP[O(log n)] has complete sets, it is not contained in BH in
any relativized world where the boolean hierarchy is infinite, i.e.,
The main result in this section is a separation of the classes P=OptP[O(log n)]
and P NP"SPARSE[O(logn)] . In fact, we show that for any fixed polynomial q there is
a relativization such that NP contains sparse sets that are not in the nonuniform
class P=q (defined as P=fh j jh(x)j - q(jxj)g).
Theorem 4.2. For every polynomial q there exists a set A such that
Proof. For an arbitrary set A we define a sparse set L(A) 2 NP A as follows.
For a given n and a suitable choosen function l(n), we partition the 2 l(n) words
of length l(n) into q(n) (with respect to the lexicographic ordering)
I l(n)
q(n)+1 such that
For each interval containing a word in A, we put a word into L(A): let w n
be an enumeration of \Sigma n in lexicographic order and let q(n). Define the
NP A set
Clearly, there are at most q(n) words of length n in A, i.e., L(A) is sparse.
Now we construct a set A in stages such that
be an
enumeration of all polynomial-time bounded Turing machines with running times
Stage g.
Stage s - 1. Choose n s minimal such that
ns
The algorithm in Figure 4.1 determines the words of length l(n s ) that are
included in A. This is done by diagonalizing against machine M s and all potential
advice for M s on an input of length n s .
Let M be any P machine. We show that M , taking advice of any q-length
bounded function, does not accept L(A). Let s be an index such that
There are 2 potential words as advice for M s on inputs of length n s (that
are stored in ADVICE). Each execution of the for-loop diagonalizes against at least
half of the possible advice for M s . Since log(2
becomes empty at the end of the algorithm. The construction further guarantees
that for every advice a, jaj - q(n s ), there exists a k - q(n s
hw ns
ns
Therefore, it suffices to show that the algorithm can always find a y 2 I l(ns)
QUERY. In every execution of the for-loop and for every advice no more than
are added to the set QUERY, i.e.,
Thus, we have for
l(ns )
ns+q(ns
contains all potential advice against that we have to diagonalize  )
QUERY := ;;
In QUERY we freeze the oracle queries of M s during the construction  )
for k := 1 to q(n s
s (w ns
if jACCj - jREJj then
remains empty, i.e., no word in ACC is advice for w ns
ns
else
put a word in I l(ns )
no word in REJ is advice for w ns
ns
choose a y 2 I l(ns)
A := A [ fyg
Fig. 4.1. Algorithm used in the proof of Theorem 4.2.
ns
by choice of n s
0:
Corollary 4.3. 9A : (NP A "
Using a "Kolmogorov-argument", Corollary 4.3 was already shown by Hema-
chandra [19]. An immediate consequence of Corollary 4.3 is the existence of an
oracle separating P=OptP[O(log n)] and P NP"SPARSE[O(logn)] .
Corollary 4.4.
5. Bounded Advice versus the Boolean Hierarchy. The levels of the
boolean hierarchy build as their union the boolean closure of NP, i.e. the smallest
class of sets that contains NP and is closed under union, intersection, and com-
plementation. In this section, we give several characterizations of the odd levels
of the boolean hierarchy. First, we show that NP machines that get as advice the
value of the k-ary characteristic function - SAT
k of SAT, where - SAT
k is evaluated on
a k-tuple that is computed from the input by an FP function, accept exactly the
languages in the (2k 1)-th level of the boolean hierarchy. The same is true if
the advice consists only of the information of how many out of k words that are
produced from the given input by an FP function are in SAT.
Cai et al. [15] give several characterizations of the boolean hierarchy, we take
the following.
Definition 5.1. A set L is in the k-th level NP(k) of the boolean hierarchy,
if there exist sets L NP such that
even
The union
k-1 NP(k) of all the levels of the boolean hierarchy is denoted by BH.
For a set A, - A denotes the characteristic function of A. - A
k is the k-ary
characteristic function of A, # A
k gives the number out of k words, that are in A,
and \Phi A
k is the parity of this number, i.e.,
# A
\Phi A
2:
The unbounded version of - A
k is - A
k .
Clearly, every set L 2 NP(k) is k-truth-table reducible to SAT, i.e., L 2
(here and in the following, the composition operator ffi takes precedence
over ==). Every set that is k-truth-table reducible to SAT is in NP(k
([28], see also [8]), thus
Since P==- SAT
closed under complementation, the classes in (5.1) are all
different unless BH (and therefore PH [20]) collapses. It is interesting to note that
a P machine needs only to know the parity of the number of k queries in SAT in
order to decide a set in P==- SAT
We show in the next theorem that the first equality in (5.2) also holds for the
nondeterministic counterparts of these classes which furthermore coincide with the
1)-th level of the boolean hierarchy. Since, as it is easily seen, NP== \Phi SAT
is contained in P==- SAT
replace P by NP, for k - 2, in the second
equality of (5.2), unless BH, and thus PH, collapse. It is an open question whether
also the classes NP== \Phi SAT
k ffiFP characterize some levels of the boolean hierarchy.
We denote the bitwise ordering on strings of the same length by -, i.e.,
Theorem 5.2.
Proof. Let L be in NP(2k 1). Then there exist sets L
that . Define the function
and let A be the set defined as
there exist I ' f2i j x 2 L 2i g and j - k
such that
it holds that x 2 L if and only if
A. To see this, observe that there is exactly one set I ' f2i j x 2 L 2i g
of cardinality f(x), namely I g. Therefore, L 2 NP==# SAT
It is clear that NP==# SAT
It remains to show that
1). For this we adapt a proof technique used by Buss
and Hay [14]. Let L be in NP==- SAT
there exist a set A 2 NP and a
function f 2 FP such that x 2 L if and only if hx; - SAT
consider the NP sets
k (f(x)); and hx; ai 2 Ag:
It is easy to see that Am ' Bm and Bm+1 ' Bm . Furthermore,
Ag.
The latter equality follows from the fact that for any x 2 Bm \Gamma Bm+1 , there is
only one string a 2 \Sigma k containing m 1's and fulfilling a - SAT
namely
k (f(x)). Therefore, x 2 L if and only if x
Hemachandra [18] (see also Buss and Hay [14]) has shown that the classes
coincide. By a slight modification in the above proof
we get the following corollary yielding a further characterization of P NP[O(logn)] .
Corollary 5.3. P==- SAT
Beigel [8] shows that
FP. From Theorem 5.2 and
the following Theorem 5.4, it follows that this equation remains valid when P is
replaced by NP. Theorem 5.4 restates an observation in [26] that # SAT
is complete
for OptP[k].
Theorem 5.4. [26]
Corollary 5.5. NP(2
Ladner, Lynch, and Selman [30] transformed the recursion theoretic truth-table
reducibility into complexity theory. They also give a definition of a nondeterministic
truth-table reduction in the following way: A is nondeterministically truth-table
reducible to B, if there exists an NP transducer G (the generator) and an NP
machine E (the evaluator) such that for every x,
there exists a branch of G(x) yielding an output
accepts.
It is known that this definition is equivalent with the nondeterministic Turing
reducibility [30] and therefore does not lead to a new reducibility notion. We
modify the above definition by restricting the generator G to be a single-valued
NP transducer, i.e., the output must be the same on every accepting branch. Let
NPSV be the set of functions computed by single-valued NP transducers [11].
This reducibility first appeared in [11] (there denoted by NP.UNIF.ALL), and
was explicitely called nondeterministic truth-table reducibility by Book and Ko [10].
Subsequently, Book and Tang [12] and Rich [35] introduced the following terminology

Definition 5.6. A set A is nondeterministically truth-table reducible to B
nondeterministically k-truth-table
reducible to B
NPSV. For a class C of sets let NP C
be the class fA j 9B
tt Bg of all sets - NP
tt -reducible to some set in C,
and let NP C
k-tt Bg.
In [11], it is shown that there exist recursive sets A and B such that A - NP
and A 6- NP
tt B. This means that - NP
tt is properly stronger than - NP
T . The question
tt is properly stronger than - NP
tt is equivalent to the P =?NP problem [11,
35]. However, as we will see in Corollary 5.8, every set A that is nondeterministically
truth-table reducible to some NP-complete set B is also deterministically truth-table
reducible to B, i.e.,
A - NP
Thus, we have the surprising result that while the definition in [30] of a non-deterministic
truth-table reduction was too weak, the definition of Rich seems
to be too strong to yield a new reduction class between fL j L - P
tt SATg and
SATg. As a further consequence of Theorem 5.7, we get a characterization
of the odd levels of the boolean hierarchy in terms of the nondeterministic
k-truth-table reducibility notion.
Theorem 5.7.
Proof. To see i) let f be in NPSV and define the NP set
For the proof of ii) define the NP set
and observe that - SAT
! (f(x)) can be read off B 0 s answers to the parallel queries
is a polynomial
bounding the running time of the NP transducer that computes f .
Corollary 5.8.
k-tt , for all k - 1,
tt .
Remark 5.9. Book and Tang [12] especially consider the O(log n) bounded
version - NP
log n-tt of the nondeterministic truth-table reduction obtained by logarithmically
bounding the number of queries produced by the NPSV generator. It follows
from (appropriately modified versions of) Theorem 5.7, Corollary 5.3, and
Lemma 3.6 that
log
log
This class is also considered by Wagner [42] (there denoted by P NP
[O(log n)]), who
shows that it coincides with the class of languages that are full-truth-table reducible 2
to SAT. As a consequence, it follows that A - NP
log n-tt SAT if and only if A is full-
truth-table reducible to SAT.
Remark 5.10. Book and Tang [12] generalized the nondeterministic truth-table
reducibility to a \Sigma k truth-table reducibility by giving the generator and the
evaluator access to a \Sigma k\Gamma1 oracle: A is \Sigma k truth-table reducible to B
. For a class C of sets let \Sigma C
k;tt be the class fA j 9B 2
Bg. Then Corollary 5.8 ii) generalizes to
i.e., every set that is \Sigma k truth-table reducible to a set in \Sigma k is already (determini-
stically) truth-table reducible to a set in \Sigma k .
2 A set A is full-truth-table reducible [28, 14] to a set B, if there is a function g 2 FP such that
for all x, g(x) is of the form ha
m), and it holds that x 2 A , a is the number whose binary
representation is given by - B
Thierauf [38] showed that allowing the generator in the nondeterministic truth-table
reduction to produce polynomially many different outputs (i.e., to compute
an NPPV function [11]) does not increase the class of sets reducible to SAT.
Theorem 5.11. [38] Let L is a set, G an NPPV transducer, and E an NP set
such that
then L is in P NP
tt .
We end this section by proving that also the strong nondeterministic truth-table
reducibility, introduced by Long [31], when applied to SAT, is only as powerful as
tt . Like in the definition of Ladner, Lynch, and Selman [30], the generator in
a strong nondeterministic truth-table reduction can produce exponentially many
different outputs, but the evaluator either has to accept all the outputs or it has
to reject all of them.
Definition 5.12. [31] A is strong nondeterministic truth-table reducible to B
B), if there is an NP transducer G and a P machine E such that for all x the
set out G (x) is nonempty, and for all hy
- A (x). For a class of sets C we denote by SN C
tt the class fA j 9B
Bg.
Clearly, - SN
tt lies in strength between - P
tt and - NP
T . Long [31] showed that - SN
is properly stronger than - NP
T by constructing two sets A and B such that A 6- SN
and A - NP
T B. The question whether - P
tt is properly stronger than - SN
tt is closely
related to two major open questions in complexity theory [31]:
Theorem 5.13. SN NP
tt .
Proof. Let L be in SN NP
tt via a generator G, an evaluator E, and a set A 2 NP.
In order to decide membership of a given input x, it suffices to find out whether there
is some output hy of G(x) such that E accepts hx; - A
)i. But this
becomes an NP problem, provided that the maximum number # A
answers from A over all outputs hy of G(x) is given along with the input
x.
More precisely, define the function
and let B be the set defined as
it holds for all x that x 2 L if and only
if hx; h(x)i 2 B, i.e., L is in NP==OptP[O(log
Note that by the above proof, Theorem 5.13 remains true if the evaluator E is
allowed to be an NP machine.

Acknowledgments

. For helpful conversations and suggestions on this work
we are grateful to V. Arvind, L. Hemachandra, and U. Sch-oning. We also thank
the two referees for their valuable suggestions.



--R

Polynomial terse sets.
Relativizations of the P
Nondeterministic witnesses and nonuniform advice.
Structural Complexity I.



Bounded queries to SAT and the Boolean hierarchy.
Probabilistic polynomial time is closed under parity reductions.
On sets truth-table reducible to sparse sets
Quantitative relativizations of complexity classes.
Characterizing Polynomial Complexity Classes by Redu- cibilities
A note on sparse sets and the polynomial-time hierarchy
On Truth-Table Reducibility to SAT

Alternation. In Journal of the Association for Computing Machinery
Computation times of NP sets of different densi- ties
The strong exponential hierarchy collapses.
Personal communication.
The polynomial time hierarchy collapses if the boolean hierarchy collapses.
P NP and sparse Turing-complete Sets for NP

Turing machines that take advice.
Relativized polynomial time hierarchies having exactly k levels.




The complexity of optimization problems.
A comparison of polynomial-time redu- cibilities
Strong nondeterministic polynomial-time reducibilities
On restricting the size of oracles compared with restricting access to the oracle.
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis.
On simultaneous resource bounds.
Positive relatvizations of the P

The polynomial time hierarchy.

PP is as hard as the polynomial-time hierarchy
Restricted relativizations of probabilistic polynomial time.
On restricting the access to an NP-oracle
Bounded query computations.
On the boolean closure of NP.
--TR

--CTR
Richard Chang, Bounded queries, approximations, and the Boolean hierarchy, Information and Computation, v.169 n.2, p.129-159, September 15, 2001
nonuniform complexity classes;truth-table reducibility;relativization;boolean hierarchy;restricted oracle access;sparse NP sets;advice classes;optimization functions