数理解析研究所講究録
第 833 巻 1993 年 31-41

31

On Using Oracles That Compute Values
関数のオラクルを用いた計算
Steve Homer ( ボストン大) \dag er

Stephen Fenner (南メイン大)*Mitsunori Ogiwara(荻原光徳 電気通信大)\ddagger

Alan L. Sehnan(ニューヨーク州立大)\S

Abstract
This paper focuses on complexity classes of partial functions that are computed inpolynomial time with oracles in NPMV, the class of all multivalued partial functions
that are coinputable nondeterministically in $olynomial$ time. oncerning deterniinistic
polynomial-time reducibilities, it is shown that
$1$

1. A multivalued$pa\iota\cdot tial$

quet ies to NPMV if)$(_{-}-$

function is polynomial-time computable with$\omega\iota do11$]} if it$i_{\mathfrak{d}}$poly nomial-tinre$Com_{1)utable}$

via

$k$

adaptive$2^{k}-1$

non-adaptive quet ies to NPMV.
2. A characteristic function is polynomial-time computable withto NPMV if and only if it is polynomial-time computable with

$k$

$k$

adaptive queries
adaptive queries

to NP.

3. Unless the Boolean hierarchy collapses, adaptive (nonadaptive) queries to NPMV
is different than $k+1$ adaptive (nonadaptive) queries to NPMV for every .
$k$

$k$

Nondeterministic reducibilities, lowness and the difference hierarchy over NPMV are
also studied. The difference hierarchy for ]functions does notunless the, the levels of the difference and bounded
Boolean hierarchy collapses, but,sets) unless the polynomial hierquery hierarchies do not interleave (as is th casearchy collapses.
$T81^{\cdot}tial$$collapt,\sim\neg e$$su1^{\cdot}p_{1}\cdot i_{S1I1}gly$$e$$fo1^{\cdot}$’Dept. of Computer Science, Portland, ME 04103. Research
Foundation under grant no. CCR-9209833.
Dept. of Computer Science, Boston, MA 01003. Research
Foundation under grant no. CCR-9103055$t_{Dept}$ . of $C_{oI11}p$ ul.er Science, $Chofu-arrow hi$ , Tokyo 18-, Japan.
Science Foundation under grant no. CCR-9002292.
$\S_{Dept}$. of Computer Science, Buffalo, NY 14260.
])).
)$F^{t}oundation$ under grant no.

$partiaJl\backslash ’\backslash ^{-}npported$by the National Science) $al\cdot(iaJl\backslash \backslash ^{\backslash }tlppo1^{\cdot}ted$by the National Science$\uparrow$$1$$Researc\cdot 1\downarrow pal(ia1]_{)^{r}}\llcorner\backslash ^{\backslash }\backslash \iota pl)orted$$Re\llcorner\backslash eal\cdot ch$$CC^{t}li- 9t$$0_{-}^{\underline{\prime}\rangle}9_{-}$$\partial 1^{\cdot}ti_{d}11\backslash \cdot\backslash ^{-}n$bv the National

pported bv the National Science32
1Introduction

In this paper we study classes of partial functions that can be computed in polynomial
time with oracles in NPMV and NPSV; namely, we study the classes $PF^{NPMV}$ and $PF^{NPSV}$ .

NPMV is the set of all partial multivalued functions that are computed nondeterministically in polynomial time, and NPSV is the set of all partial functions in this class that are
single-valued. NPMV captures the complexity of computing witnesses to problems in NP.
For example, let sat denote the partial function defined by -scxt $(x)$ maps to a value if andonly if encodes a formula of propositional logic and encodes a satisfying assignment of. Then, sat belongs to NPMV, and the domain of sat (i.e., the set of all words for which
the output of sat
is non-empty) is the NP-conrplete satisfiability problem, SAT. Also,
NPMV captures the complexity of inverting polynomial timefunctions. To wit, theinverse of every polynomial time honest function belongs to NPMV, and the inverse of every
one-one polynomial time honest function belongs to NPSV.
The class of partial functions with oracles in NP, namely, $PF^{NP}$ has been well-studied[Kre88], as have been the corresponding class of partial functions that can be computed[Se192], and the classes of partial functions
nonadaptively with oracles in NP, viz.
, namely, $PF^{NP[k]}$that are obtained by limiting the number of queries to some value Ar[Bei91]. A rich $bod$ } of
.
and
is
about
cla.
Here we raise the question, “what is the difference between computing with an oracle. If the partial function sat is
in NPMV versus an oracle in NP.” The
is notprovided as an oracle to some polynomial-time computation. then on a query , where
encodes a satisfiable formula of propositional logic, the oracle will return some satisfying
assignment . However, if the oracle to A4 is the NP-compete set SAT, then to this query, the oracle will only return a Boolean vaJue‘yes.” On the other hand, by the well-known
self-reducibility of SAT, $M$ could compute for itself by judicious application of several
adaptive queries to SAT. Indeed $Theore\ln 1.1$ states that unbounded access to an oracle in
NPMV is no more powerful than such an access to an oracle in NP. However, in Section 3
we will see that the situation for bounded query classes is much more subtle. In general,
function oracles cannot be replaced by set oracles–but set oracles are still useful. We willshow that every partial function in $PF^{NPMV[k]}$ can be computed b.v a partial function of theform $fog$ , where is in NPMV and belongs to $PF^{NP[k]}$ . Moreover, most surprisingly,
the relationship between access to an oracle in NPMV and acce, to an oracle in NP is. This means that when we aretight regarding set recognition; that is,computing characteristic functions, bounded queries to an oracle in NPMV give no more
information than the same number of queries to an oracle in P.
$y$

$x$

$y$

$x$

$x$

$(\backslash \iota\cdot)$$1_{1O11}est$$PF_{tt}^{NP}$$\geq 1$$PF_{tt}^{NP[k]}$$1^{\cdot}esult,-\backslash$$]_{\backslash no\backslash \{}\cdot n$$ans\backslash ver$$\iota 1\iota e\overline{\backslash }e$$\backslash ^{\neg}se\backslash \neg$$obviou\backslash$$\lrcorner 1l$

$x$

$x$

$y$

$x$

$y$

$f$

$jC$

$\backslash -\backslash \neg$$P^{NPM\vee[\Lambda\cdot]}=P^{NP[\lambda\cdot]}$$k$$\wedge\nwarrow^{\tau}$

33
We will show that the levels of the nonadaptive and adaptive bounded query hierarchies
interleave (for example, adaptive queries to a partial function in NPMV is equivalent to$2^{k}-1$ nonadaptive queries to a partial function in NPMV), and we will show that thesebounded query hierarchies collapse only if the Boolean hierarchy collapses.
In Section 4 we study nondeterministic polynomial time reductions to partial functionsin NPMV. Unlike the case for deterministic functions, we will see that just one query to
an NP oracle can substitute for an unbounded number of queries to any partial function in
NPMV. The hierarchy that is formed by iteratively applying NP reductions is an analogue$k$of the polynomial hierarchy, and we will sho . that this hierarchy collapses if and only if
the polynomial hierarchy collapses.
In Section 5 we will study the difference hierarchy over NPMV. We define $f-g$ to be apartial function that maps to if and only if maps to and does not lnap to , andwe define NPMV $(k)=$ { $f_{1}-(f_{2}-(\cdot\cdot-f_{k}))$ :NPMV}. Since the propertiesof the bounded query hierarchies over NPMV are largely similar to those over NP, one
might hope that the same thing happens here–that the query hierarchy over NPMV andthe query hierarchy over NP are similar. However, the contour of this hierarchy is, to ourastonishment, totally different than its analogy for NP. Although BH $=\cup kNP(k)\subseteq P^{NP}$ ,with no assumption, we will show that NPMV(2) is included in $PF^{NPMV}$ if and only if. Also, in this section we will introduce the notion of NPMV-lowness, and we willPHgive a complete characterization of NPMV-lowness.
Consideration of reduction classes with oracles in NPSV, to be studied in Section 6,
is motivated in part by a desire to understand how difficult it is to compute satisfying
assignments for satisfiable formulas. The following technical notions will help to make thisclear. Given partial multivalued functions
and , define to be a refinement of if$dom(g)=dom(f)$ and for all
and all , if is a value of $g(x)$ , then is a valueof $f(x)$ . Let
and be classes of partial multivalued functions. Purely as a convention, if
is a partial multivalued function, we define
if contains a refinement of , andwe define
if for every. Let PF denote the class of partial functions
that are computable deterministically in polynomial time. The assertion “NPMVPF”
would mean that every partial multivalued function in NPMI’v has a refinement that can becomputed efficiently by some deterministic polynomial time transducer. It is well-known
that.; $at$
PF if and only if NPMV
if and $on$ ] if $P=$ NP [Se192]. Thus, one
does not expect that $sat\in_{c}$ PF. Is sat computable in some larger single-valued class ofpartial functions? It is shown in [Se192] that PF
NPSV. and it is an open
question whether $sat\in_{c}$ NPSV or whether. X
will consider classes of the$PF^{NPSV[k]}$, where $k\geq 1$ , and we will show that the adaptive and theform
and$\backslash \iota$

$x$

$f$

$y$

$x$

$f_{1},$

$g$

$y$

$x$

$y$

$\cdots,$ $f_{k}\in$$=\triangle_{2}^{P}$$f$$x\in do\uparrow 7x(g)$$\mathcal{F}$$\mathcal{G}$$f$$f\in_{c}\mathcal{G}$$\mathcal{F}\subseteq_{C}\mathcal{G}$

$y$

$y$

$y$

$f$

$g$

$g$

$f\in \mathcal{F},$$\mathcal{G}$

$g$

$f$

$f\in_{c}\mathcal{G}$$\subseteq_{c}$$\subseteq_{(}- PF$$\in_{c}$

$y$

$-$

$\subseteq$$\underline{\overline{:}}at\in_{c}PF_{tt}^{NP}$$PF_{tt}^{NPSV[k]}$$\subseteq PF_{tt}^{NP}$$l\cdot e$

34
nonadaptive classes form proper hierarchies unless the Boolean
these classes form a finer classification in$n$$hiel\cdot al\cdot chy$collapses. Thus,

hich to study the central question of whether

sat has a refinement in some interesting class of single-valued partial functions.
Finally, we note in passing that the complexity theory of decision problems, i.e., of sets,
is extremely well developed. Although the computational problems in which we are mostinterested are naturally thought of as partial multivalued functions, the structural theory
to support classification of these problems has been slight. By introducing several natu-

ral hierarchies of complexity classes of partial multivalued functions. with strong evidence

supporting these claims, we intend this papeI to make significant steps in correcting thissituation.

Preliminaries

2

We fix$\Sigma$to be the finite alphabet $\{0,1\}$ . Letfunction. We write $f(x)-fy$ , if$f$:

be a partial multivalued$\Sigma^{*}\mapsto\Sigma^{*}$

on input string . Define graph $(f)=$) $x(f)=\{x|\exists y(f(.\iota\cdot)-y)\}$ , and $\uparrow((’\iota ge.(f)=\{y|\exists x(f(x)\mapsto ry)\}$ .
$\{\{x, y\}|f(x)-y\},$We will say that is undefined at if.
A transducera read-only input tape, a
is a nondeterministic Turing machine
write-only output tape, and accepting states in the usual manner.
computes a value
on an input string if there is an accepting computation of
on.i: for whichis the) Such transducers
final content of $T’ s$ output tape. (In this case, we
compute partial, multivalued functions. (As transducers do not typically accept all input“, “partial function” is $a1n$.ays intended. If a function isstrings, when we write :total, it will always be explicitly noted.)$y$is a value of

$f$

$x$

$do\uparrow$$\cdot$$f$$\tau\cdot\not\in do\prime 7t(f)$

$x$

$T$

$\backslash vith$

$T$

$y$

$T$

$x$

$y$

$wil1\backslash \iota^{r}1^{\cdot}iteT(x)-y.$

$f$

.
.
.

NPMV is the set of all partial, multivalued functions computed by nondeterministic
polynomial time-bounded transducers;

NPSV is the set of all $f\in$ NPMV that$aI^{\cdot}e$single-valued:

PF is the set of all partial functions computed by deterministic polynomial time-bounded transducers.

$PF^{NP}$is the class of functions computed in polynoinial$ti_{1}l$) $e$with oracles in NP.

is the class of functions that can be coinputed nonadaptiv ely witha partial function$f$that $f\in PF^{NP}$ via

$T$

is in

$PF_{tt}^{NP}$$01^{\cdot}acles$

in NP; that is,

such
in NP and a polynomial time computable function

if there is an oracle Turing machine transducer

with an oracle$L$$PF_{tt}^{NP}$

$T$

35
$f$

: $\{0,1\}^{*}-r(c\{0,1\}^{*})^{*}$ such that, for each input$x$

to $T,$$T$

onlv makes queries to

$L$

from

the list $f(x)$ .
Now we describe oracle Turing machines with oracles that compute partial functions.
be a
For the moment, we assume that the oracle is a single-valued partial function. Letsymbol not belonging to the finite alphabet . In order forto access a partial function$\perp$$-t’I$$\Sigma$oracle, $M$ contains a write-only input oracle tape, a separate read-only output tape, and a

special oracle call state . When $M$ enters state , if the string currently on the oracle input
$q$

$q$

tape belongs to the domain of the oracle partial function, then the result of applying theoracle appears on the oracle output tape, and if the string currently on the oracle input tapedoes not belong to the domain of the oracle partial function, then the $symbol\perp$ appears on
the oracle output tape. Thus, if the oracle is some partial function , given an input tothe oracle. the oracle, if called, returns a value $g(x)$ if one exists, and returns
otherwise.
$x$

$g$

$\perp$The oracle may not provide its own input, so that any change to the oracle input must be
made by M. (It is possible that $M$ may read only a portion of the oracle’s output if theoracle’s output is too long to read with the resources of $M.$ )If is a single-valued partial function and AI is a deterministic oracle transducer as justdescribed, then we let $M[g]$ denote thepartial {unction computed by $M$ with$g$$single-\backslash \cdot alue(1$oracle .
$g$

Definition 1 Let
polynomial time,valued refinement
Let$\mathcal{F}$$f$is Turing reducible to in
be multivalued partial $fu$ nction.-.
, if for some deterministic oracle tran.sdzt $cerM$ , for every singleof $J/l[g’]$ is $sinc$) le-valned refinement of

and

$f$

$g$

$g$

$f\leq_{T}^{P}g$$g’$$f^{1}$$a$$g,$

be a class of partial multivalued functions.

multivalued functions$f$that are$\leq_{T}^{P}$-reducible to some$PF^{\mathcal{F}}$$g\in \mathcal{F}$.

denotes the class of partial$PF^{\mathcal{F}[k\cdot]}$(respectively, PF $iF[\log]$ )-reducible to somedenotes the class of partial multivalued functions that
adaptive
via a machine that, on input , makes adaptive queries ( pectively,
queries) to its oracle.
-reducible to somedenotes the class of partial multivalued functions that are
via an oracle Turing machine transducer that queries its oracle nonadaptively.
$f$

$x$

$al\cdot e\leq_{T}^{P}$$k$$g\in \mathcal{F}$$\mathcal{O}(\log|x|)$$1^{\cdot}e-\backslash$$PF_{tt}^{F}$$f$$\leq_{T}^{P}$$PF_{tt}^{\mathcal{F}[k]}$$g\in \mathcal{F}$1

A notion of polynomial-time Turing reducibility between
functions is defined in [Se192]. It is
important to note that the definition given here is different than the one in [Se192]. Here the oracle “knows“$pa\iota\cdot tial$

when a query is not in its domain. In the earliel definition,
is not the case. The authors recommend thatis the conimon notation for
the reducibilitv defined in [Se192] should in the future be denoted as$1^{\cdot}ecoIllltlendation$][)$eI11S$
conceptually and technically. We make thisreductions between
this reducibility between functions is equivalent to a promise $P^{lobleI11}$ reduction. Also, we note that the. In
nla l . it is easv to see that iterating
reducibility defined in [Se192] is not useful for
purposesis endowed with the
reductions between functions in NPMV does not gain anvthing new unless he$\cdot$$thi\backslash$$\leq^{P_{1}.P},$$proI11i\backslash _{-}eP^{ro)}|$$\iota\backslash hic1_{1}$$eca\backslash \iota h_{-}e$$oU1^{\cdot}$$hel\cdot e$$pa\iota tic$$\cdot$$t$ability to know its domainl$01^{\cdot}acle$

36-reducible to somedenotes the class of partial multivalued functions that are
via a machine that makes nonadaptive queries to its oracle.
, respectively, denote the classes of all characteristic
and$f$$g\in \mathcal{F}$$\leq_{T}^{P}$$k$$P^{\mathcal{F}},$$P^{F[k]},$$P^{\mathcal{F}[\log]},$$P_{tt}^{\mathcal{F}[k]}$$P_{tt}^{\mathcal{F}}$.
, we may say that
denotes the class of partial single-valued
functions that are-reducible to the characteristic function of some set in C. (Note that, and.
functions inare single-valued.).
. .
are defined similarly.
Obviously $PF^{NP}\subseteq PF^{NPMV}$ . Conversely, for a function $f\in$ NPMV, define $f’$ to be afunction such that $f’(x)= \min\{y:f(x)\mapsto y\}$ . $f’$ is a single-valued refinement of and infunctions contained in
For a class of sets$PF^{\mathcal{F}},$$PF^{F[k]},$$PF^{\mathcal{F}[\log]},$$PF_{tt}^{\mathcal{F}}$and$PF_{tt}^{\mathcal{F}[k]}$$PF^{C}$$C$$\leq_{T}^{P}$$PF^{C}$$PF^{C[k]}$$PF^{C[\log]}$$P\Gamma_{tt}^{C}\prec$$P^{C},$$PF_{tt}^{C[A\cdot]}$$P^{C[k]},$$P^{C\beta og]},$$P_{tt}^{C}$$P_{tt}^{C[k]}$$f$$PF^{NP}$. Therefore, the following theorem holds.

Theorem 1 $PF^{NPMV}\subseteq_{c}PF^{NP}$ . That is, every $f\dot{n}nction$ in $PF^{NPMV}$ has a single-valued
refinement in $PF^{NP}$ .
Consider the function maxclique that on input a graph$C_{1^{1}}$outputs a clique of maximum

has a clique. Then, maxclique is a multivalued partial function that belongs to$PF^{NPMV}$ . Similarly, the following function maxTsat is a multivalued partial function thatsize, if$G$

belongs to $PF^{NPMV}$ .
$maxTsat(x)rightarrow y$ , if $y$ isa satisfying assignment of$x$with the maximum number of true’s.

Let be a function that maps a pair $(x, n)$ to if and only if is a satisfying assignmentof withtrue’s. Since the number of variables in a formula is bounded by its length,$1\leq n\leq|x|$ such that
it holds that maxTsat(x) $=f(x, n_{x})$ , whereis the largest
$f$

$x$

$y$

$y$

$n$

$n_{x}$$\uparrow\iota,$$(x, n)\in dom(f)$ . This implies that $\prime naxTsat\in PF_{tt}^{NPMV}$ .

We should note that several of the classes we investigate here seem to capture thecomplexity of finding witnesses to NP-optimization problems. This observation is exploredby Chen and Toda [CT92] and by Wareham [War92].
Theorem 1 states that unbounded access to an oracle in NPMV is no more powerfulthan such an access to an oracle in NP.

3

Bounded Query Classes

Now we state our main results; proofs are given in the full draft paper. Generaltechniques developed in this section are reminiscent of the \langle mind-change‘‘ technique of[Bei91, KSW87].

37
Theorem 2 For eve$r\cdot yk\geq 1,$$PF^{NPMV[k]}=PF_{tt}^{NPMV[2^{k}-1]}\subseteq_{C}$$PF_{tt}^{NP[2^{k}-1]}\subseteq PF^{NPMV[k+1]}=PF_{tt}^{NPMV[2^{k+1}-1]}$

NPMV $oPF^{NP[k]}\subseteq NPMVo$.

For general bounded query classes, it is not known whether $PF^{NPMV[k]}\subseteq {}_{c}PF^{NP[k]}$ . But,
for reduction classes of sets, this type of equivalence holds.
Theorem 3 For every $k\geq 1,$ $P^{NPMV[k]}=P^{NP[k]}$ .
Theorem 4 For every $k\geq 1,$ $P_{tt}^{NPMV[k]}=P_{tt}^{NP[k]}$ .
We denote the k-th level of the Boolean hierarchv as $NP(k)$ . By definition,.
.

NP(1) $=NP$ , andfor every $k\geq 2,$ $NP(k)=NP-NP(k-1)$ .

The Boolean hierarchy over NP, denoted by BH is the union of all $NP(k),$ $k\geq 1$ .
The following theorems give evidence to show that bounded query hierarchies do notcollapse.
Theorem 5 Let $k\geq 1$ . If $PF^{NPMV[k+1]}=PF^{NPM\backslash [k]}f$ then BH collapses to its
Theorem 6 Let $k\geq 1$ . If

$PF_{tt}^{NPMV[k+1]}=PF_{tt}^{NPM\lambda^{\gamma}[k]}$$2^{k}$-th level.

. then BH collapses to its $(k+1)- st$level.
Analogous to the theorems stated so far, the following theorems hold for reduction
classes that make logarithmic many queries to partial functions in NPMV.

Theorem 7

1. $PF^{NPMV[\log]}=PF_{tt}^{NPMV}$ .

2. NPMV $oPF^{NP[\log]}=$ NPMV
3.

$PF^{NPMV[\log]}\subseteq_{c}$4. NPMV
Theorem 8$oPF_{tt}^{NP}$.

NPMV $oPF^{NP[\log]}$ .

$oPF^{NP[\log]}\subseteq PF^{NPMV[\log]}$.

$P^{NPMV[\log]}=P_{tt}^{NPMV}=P^{NP[\log]}=P_{tt}^{I\backslash \mathfrak{s}p}$.

384Nondeterministic Polynomial-Time Reductions
We define nondeterministic reductions between partial functions so that the access mechbe a single-valued
anism is identical to that for deterministic reductions. Namely, let$f$partial function and $N$ be a polynomial-time nondeterministic oracle Turing machine. $N[f]$denotes a multivalued partial function computed by $N$ with oracle in accordance with the$f$following mechanism:.
.

when $N$ asks about $y\in dom(f),$$f$returns $f(y)$ andwhen $N$ asks about $y\not\in dom(f),$$f$answers a special symbol

Let

$f$

and

$g$

be multivalued partial functions.

We$\overline{\backslash }a\backslash \sim$$\perp$. that.
$f$

is nondeterministic

polynomial-time Turing reducible to , denoted by $f\leq_{T^{P}}g$ if there is a polynomial-timenondeterministic Turing machine $N$ satisfying the $follon\cdot ing$ conditions: for every and forevery single-valued refinement of ,
$g$

$x$

.
.

$g’$

$g$

$x\in dom(f)$ if and only if $x\in dom(N[g’])$ and

if $N[g’]$ maps

to

$x$

$y$

, then $f$ maps

$x$

to .
$y$

In other words, $N[g’]$ is a refinement of .
$f$

Let

$\mathcal{F}$be a class of partial multivalued functions.

multivalued functions that are$\leq_{T}^{NP}$-reducible to someof partiaJ multivalued function, that are
makes adaptive queries to its.
$\backslash$some$g\in \mathcal{F}$$\leq_{1}^{N_{-}P}$$g\in \mathcal{F}.$-reducible todenotes the class of partial
denotes the class

NPMI’$\backslash 0|1\iota eg\in \mathcal{F}$via a machine that$01^{\cdot}acle$$k$$NPMV_{tt}^{\mathcal{F}}$$NPM\backslash ;F$denotes the class of partial multivalued functions that are

via a machine that makes nonadaptive queries to its oracle.

the class of partial multivalued functions that are$\leq_{T}^{NP}$$\leq_{T}^{NP}$-reducible to$NPMV_{tt}^{F[k]}$-reducible to somedenotesvia a$g\in \mathcal{F}$machine that makes nonadaptive queries to its oracle.
For a class of sets , we write $NPMV^{C}$ to denote the class of multivalued partial functions that are computed by an nondeterministic Turing machine relative to an oracle in .
and $NPMV_{tt}^{C[k]}a.re_{NPM\vee}defined$ similarly.
$k$

$C$

$C$

$NPM\backslash \gamma C[k]NPMV_{tt}^{C}$For$k\geq 1,\underline{\backslash ^{\backslash }}Ml_{k}’$denotes $\frac{NPM\backslash /}{k}$ .

Lemma 1 For every $k\geq 1,$ $\Sigma MV_{k}=$ NPMV$\Sigma_{k}^{p}$$\Sigma_{k-1}^{\rho}[1]m|.rl$.

From this lemma we yield the following theorent.

for}$\epsilon L^{\backslash }C’$$yf\in\Sigma M\backslash I_{k}dom(f)\in$39
Theorem 9 Let be a partial multivalued func tion. For
ments are equivalent:
$f$

(i)

is in

$f$

(ii)

$f$

(iii)

$f$

$\Sigma MV_{k}$the following state-$\epsilon\iota\cdot\epsilon\uparrow\cdot yk\geq 1_{i}$;is polynomially length-bounded, do$7?\iota(f)\in\Sigma_{k}^{p}$

is polynomially length-bounded and, and$g\uparrow aph(f)\in\Sigma_{k}^{p}$

Theorem 10 For every $k\geq 1,$ $\Sigma MV_{k+1}=\Sigma MV_{k}$ if and$g7^{\cdot}c\iota ph(f)\in\Sigma_{k}^{p}$;.
$0\prime\prime lyiJ^{\cdot}\Sigma_{k+1}^{p}=\Sigma_{k}^{p}$.

Thus, these classes form function analogues of the polynomial hierarchy, and, unless thepolynomial hierarchy collapses, they form a proper hierarchy.

5

The Difference HierarchyLet.

$co\mathcal{F}$$\mathcal{F}$be a class of partial multivalued functions. A partial multivalued function

if there exist$g\in \mathcal{F}$$f(x)$ maps toLet$\mathcal{F}$

and

$y$

and a polynomial

such that for$p$$evel\cdot yt\iota$

. and

$y$

$\mathcal{F}\wedge \mathcal{G}$$x$$/\iota(x)$.

and$h(x)$$\mathcal{F}-\mathcal{G}$maps to$g\in \mathcal{G}$$y$if and only if$h$$f(.\iota\cdot)$is insuch that for every

maps todenotes$f\in \mathcal{F}$and$g\in \mathcal{G}$

such

$y$

A partial multivalued function$f\in \mathcal{F}$$y$if and only if $|y|\leq p(|x|)$ and $g(x)$ does not map to .

function is in
if there exist partial multivalued functions
that for every and ,

.

is in

be two classes of partial multivalued functions. A partial multivalued$\mathcal{G}$

$h$

$f$

$y$

$x$

maps to$\mathcal{F}\vee \mathcal{G}$

and

$y$

and

$g(\tau\cdot)$

maps to .
$y$if there exis partial multivalued functions$t$,

if and only if $f(x)$ maps to$\mathcal{F}\wedge co\mathcal{G}$

$y$

$y$

or $g(x)$ maps to .
$y$.

NPMV $(k)$ is the class of partial multivalued functions defi ned in the following way:
1. NPMV(I)$=$NPMV, and2. for $k\geq 2,$ $NPMV(k)=NPMV-NPI\backslash /IV(k-1)$ .
Lemma 2 For every $k\geq 1,$ $f\in NPMV(k)$ if and$0’\iota ly$

if

$f$

is polynomially length-bounded

and graph $(f)\in NP(k)$ .
This lemma is proved by induction.

$11/^{\vee}e$

use it to obtain the following theorem.

40
Theorem 11 For eve $ryk\geq 1,$ $NPMV(k+1)=$ NPMV $(k)$ if and only if $NP(k+1)=$
NP $(k)$ .
Theorem 12 NP$=$

co-NP if and only if NPMV$\subseteq coNP_{\sim}^{1}\backslash 1l’$

if and only if coNPMV$\subseteq$

NPMV.
A function$f$is said to be NPMV-low if NPMV $f=$ NPMV.

Theorem 13 A function
co-NP.
Theorem 14 NPMV(2)Theorem 15$f$

is NPMV-low if and only if $f\in$ NPMV rvith $dom(f)\in NP\cap$$\subseteq_{C}PF^{NPMV}$$PF^{NPM\vee[k]}\subseteq$

if andif$\cdot$$olt./y$$\Sigma_{2}^{p}=\triangle^{\underline{\rho_{)}}}$.

NPMV $(2^{k+1}-1)$ .

By Theorem 11, the levels of the difference hierarchy of partial functions are distinct if
and only if the same levels of the Boolean hierarchy are distinct. Yet, whereas the Boolean
hierarchy resides entirely within$P^{NP}$, by Theorem 14, this is unlikely to be true of thedifference hierarchy of partial functions.

6

Reduction classes to NPSV
, $PF^{NPSV[k]},$ $PF^{NPSV[\log]}$ ,In this section, we study the reduction classes to NPS, and. These classes contain only single-valued functions. The following$P\}^{\neg NPS\backslash }1$$\backslash ^{\sim},$$PF_{tt}^{NPS\vee}$$PF_{tt}^{NPS\vee[k]}$proposition is easy to prove.
Proposition 1

1. $PF^{NP}=PF^{NPSV}$ and$PF_{tt}^{NP}=PF_{tt}^{NPS\backslash j}$

2. $PF^{NP[k]}\subseteq PF^{NPSV[k]}\subseteq PF^{NPMV[k]}$ and $PF^{NP[\log]}\subseteq PF^{NPS\backslash [\log]}’\subseteq PF^{NPMV[\log]}$ .

3.

$PF_{tt}^{NP[k]}\subseteq PF_{tt}^{NPSV[k]}\subseteq PF_{tt}^{NPM\vee[k]}$4.

$P_{tt}^{NP}=P_{tt}^{NPSV}$

and $P^{NP}=P^{NPSV}$ .

5. $P^{NP[k]}\subseteq P^{NPS\vee[k]}\subseteq P^{NPMV[k]}$ and6.

.

$P_{tt}^{NP[k]}\subseteq P_{tt}^{NPSV[k]}\subseteq P_{tt}^{NPMV[k]}$$P^{NP[\log]}\subseteq P^{NPSV[1_{0_{5}^{\circ}}]}\subseteq P^{NPM\backslash [[\log]}$.

.

The following theorems follow as corollaries of results proven in the previous sections.

Theorem 16 For every $k\geq 1,$ $P^{NPSV[k]}=P^{NP[k]}$ .

41
Theorem 17 For every $k\geq 1,$$P_{tt}^{NPSV[k]}=P_{tt}^{\aleph^{1P[k]}}$.

Theorem 18 If $PF_{tt}^{NPSV[k+1]}=PF_{tt}^{NPSV[k]}f\dot{o}\uparrow$ . so nze $k\geq 1$ . thlevel.

$\xi\prime 7$

BH collapses to its $(k+1)-$$st$

Theorem 19 If $PF^{NPSV[k+1]}=PF^{NPS\iota^{\gamma}[k]}$ for some $k\geq 1$ . then BH collapses to its$2^{k}$-thlevel.

参考文献[Bei91]

R. Beigel. Bounded queries to SAT and the boolean$Sc$[CT92]$hiel\cdot al\cdot chy$

. Theor. Computerience, $84(2):199-223$ , 1991.

Z. Chen and S. Toda. On the complexity of computing optimal solutions. Department of Computer Science and Information Mathematics, University of ElectroCommunications, Chufo-shi, Tokyo 182. Japan, 1992.

[Kre88]M. Krentel. The complexity of optimization )$1$$1^{\cdot}01$) $letllS$. J.

$Ci’ 0\uparrow 7tp$

zt $ter$ Systems Sci.,

36:490-509, 1988.

[KSW87] J.

$K\ddot{o}$blel , U. Schoning, and K. Wagner. The difference and truth-table hierarchies$\cdot$for NP. Theotetical Informatic. and.4 ])$-\backslash$[Se192]$/ic\cdot c/t/0\prime\prime.\backslash (1i\lrcorner 414RO),$$21:419-435$ , 1987.

A. Selman. A taxonomy of complexity classes of functions. J. C’omput. Sytsem
Sci., 1992.

[War92]

$p$

$\ln$

press.

H. Wareham. Masters thesis. Department of Computer Science, Memorial Uni-

versity of Newfoundland, 1992.