The Complexity of Decision Versus Search.
A basic question about NP is whether or not search reduces  in polynomial time to decision.  This paper indicates that  the answer is negative: Under a complexity assumption (that  deterministic and nondeterministic double-exponential time  are unequal) a language in NP for which search does not  reduce to decision is constructed.  These ideas extend in a natural way to interactive proofs  and program checking.  Under similar assumptions, the  authors present languages in NP for which it is harder to  prove membership interactively than it is to decide this  membership, and languages in NP that are not checkable.
Summary

. We summarize relationships amongst the various complexity classes wehave discussed.
First, some notation. We de ne the triple exponential time class
Similarly,we let BPEEE denote the class of languages recognized with bounded error by a probabilistic
nTM running in time 222 for some constant c 0.
The following inclusions are known, or easily derived from known techniques:
3 compIP Check frIP MIP Coh.
Under the assumption NEE BPEE we establish the following:4 NP is not contained in any of the following: compNP; compIP; Check; frIP.
5 NP Coh is not contained in any of the following: compNP; compIP; Check; frIP.
For the results of line 4 , see Theorems 2.9, 4.4, 5.3 and 3.6. For those of line 5 , see the theorem
and discussion at the end of Section 5. Finally, under the assumption NEEE BPEEE , BFestablish the following:
6 NP Coh.2 Decision versus SearchinNP
In this section we present a simple construction of a language in NP for which searchdoesnot
reduce to decision, assuming that EE NEE. In later sections we will extend the argumenttointeractive proofs and program checking. Let us begin with the de nitions.
2.1 De nitions
The goal of this section is to make precise what we mean by search reduces to decision for an NP
language L." Since the issues were discussed at length in Section 1.1,we will here be brief, stating
the formal de nitions and limiting the discussion to essentials.
It is convenient to proceed in steps. We begin by de ning NP-relations and saying what it
means for search to reduce to decision for them. We then use this this to say what it means for
search to reduce to decision for a NP language.
De nition 2.1 Let ; beapolynomial time computable binary relation, and let x 2f0; 1g .
We let x f w and call the members of this set -witnesses for x.We
say that is an NP-relation if there exists a constant c 2 N such that for all x 2f0; 1g it is the
case that x f0; 1gjxjc. The language de ned by is f x 2f0; 1g : x ;gand is denotedL .
Note that if is an NP-relation then L 2 NP.
Notation: If W is an oracle machine, then WL x denotes the output of W with oracle L
f0; 1g and input x 2f0; 1g .
Wenowsay what it means for search to reduce to decision for an NP-relation. An equivalent
formulation of the de nition that follows appears in BD .
De nition 2.2 Suppose is an NP-relation and W isapolynomial time oracle machine. Let
L L . We say that W is a -witness nder if for each x 2 L it is the case that WL x 2 x .
We say that search reduces to decision for if there exists a -witness nder.
Note that the witness nder is not restricted to any particular method for example, it is not required
that the length of queries be decreasing with time . Rather, any polynomial time computation is
allowed. This strengthens negative results.
Wenow wish to say what it means for search to reduce to decision for an NP language as
opposed to an NP-relation . Begin with the following terminology.
De nition 2.3 Suppose is an NP-relation and L f0; 1g is a language. We say that de nes
Clearly, there exists an NP-relation which de nes L. However, for any particular
language L 2 NP, there may be many di erent NP-relations which de ne L.IfL is NP-complete,
then search reduces to decision for any of these NP-relations. However if L is not NP-complete,
then search might reduce to decision for some of them but not for others. In de ning what it means
for search to reduce to decision for L wehavechosen to be liberal: we ask only that there be some
NP-relation de ning L for which search reduces to decision.
De nition 2.4 Suppose L f0; 1g . We say that search reduces to decision for L if there exists
an NP-relation such that de nes L and search reduces to decision for .
As wehave indicated in Section 1, our de nition is motivated byinteractive proofs and the question
of whether proving membership is harder than deciding it. Proving membership in L is easy in
the sense that L has a competitive NP-proof system as long as search reduces to decision for some
NP-relation de ning L,sowe are led to De nition 2.4. We note, in this context, that there are
languages suchasf0; 1g which are easy but have an associated search problem which is hard
and we certainly don't wish to think of search as being harder than decision for these languages.
Appropriately, search does reduce to decision for these languages according to our de nition.
Finally,we note that the existence of a language for which search does not reduce to decision
does, of course, imply the existence of an NP-relation for which search does not reduce to decision,
so negative results under our de nition are stronger than those which simply conclude the existence
of NP-relations for which search is harder than decision.
Whenever is understood we will say witness" or   witness    nder" rather than -witness" or
-witness nder."
2.2 Uniformly Log-Sparse Languages
Our proof will use languages which combine logarithmic sparseness with the property that it be
possible to e ciently identify a logarithmic sized superset of the strings belowany given length.
Let us proceed to the formal de nitions.
De nition 2.5 The census function L : N N of L f0; 1g of a language L is de nedby
We say that L is log-sparse if L n O logn .
That is, L n is the number of strings in L whichhave length n, and a language is log-sparse if
it contains at most O log n strings of length at most n. Log-sparse languages were used in HSI
where they were called
The next de nition formalizes the idea of being able to e ciently identify some super-set of a
language, and then speci es the notion of uniform log-sparseness" in whichwe are interested.
De nition 2.6 We say that C f0; 1g is a candidate selector for L if C is polynomial time
decidable and L C. We say that a language L is uniformly log-sparse if it has a log-sparse
candidate selector.
As we will see in Section 2.3, the interest of uniformly log-sparse languages is that they form a class
for which the problem of reducing search to decision is particularly hard. Let us end this section
by stating a lemma whichwe will use later. This lemma generalizes work of Hartmanis, Sewelson
and Immerman HSI , who showed that there is a log-sparse language in NP , PifE NEE. yLog-sparseness is weaker than uniform log-sparseness in that no candidate selector is required, but
it is easy to see that a uniformly log-sparse language in NP , P nonetheless exists under the same
assumption. For completeness we provide a sketch of the entirely standard proof.
Lemma 2.7 If EE NEE then there is a uniformly log-sparse language in NP , P.Proof: We use a standard downward separation" argument. Assume EE NEE and suppose
ne that L is uniformly
log-sparse and L 2 NP , P.
y HSI claimed the converse as well, but Allender Al points out that their proof is awed and the theorem cannot
be proved using techniques that relativize.
De ne A to be the algorithm which on input x 2f0; 1gn behaves as follows. If n is not in the range
of g then A outputs 0. Else it computes k g,1 n and outputs 1 i the last n , k bits of x are
zero. Then C f x : A x 1g is a candidate selector for L and C n 21+g,1 n O logn ,
so L is uniformly log-sparse.
The fact that L 2 NP , P follows directly from the fact that L0 2 NEE , EE.
2.3 A Language for which Search Does not Reduce to Decision
The following, which is the main lemma of this section, shows that the reduction of searchto
decision for a uniformly log-sparse language is only possible in the trivial case where the language
is already in P.
Lemma 2.8 Suppose L is a uniformly log-sparse language for which search reduces to decision.
Proof: By assumption, there exists an NP-relation and a polynomial time oracle machine W
such that de nes L and W is a -witness nder. We will construct a polynomial time machine
which decides L.We begin by describing the idea informally.
The idea is to use W as a subroutine to nd a witness. The di culty is, of course, that W makes
oracle queries about L itself. Not having access to an oracle for L, our machine M certainly cannot
correctly answer these queries. To see how it can nonetheless exploit W, suppose for a moment
that W is guaranteed to make only one oracle query in its entire computation on input x. Then
can try both possible answers. That is, it branches into a pair of parallel computations. In the
rst it answers the query by 0 and in the second it answers it by 1, and in both cases it then runs
W until W halts. Clearly x 2 L if and only if at least one of these runs outputs a witness, and the
strategy is polynomial time.
This idea extends to W making O log n queries. In reality,however, W could make polynomially
many queries so that this strategy is not e cient. This is the point where weinvoke the uniform
log-sparseness of L whichwehave not used so far . This implies that there are really only O log n
e ective" queries that W can make: since W can only write down queries of polynomial length,
we can use the log-sparse candidate selector of L to identify a set of at most O log n strings which
include all strings in L which W could possibly query, and we need branch only on these.
With this overall strategy in mind let us now specify the operation of M more precisely. Since
is an NP-relation, there exists a constant c 2 N such that for all x 2f0; 1g it is the case that
x f0; 1gjxjc.We can assume that there is a constant d 0 such that on any input x 2f0; 1g
the machine W will halt in djxjd steps and output a string of length jxjc, regardless of how the
oracle queries of W are answered. We also assume wlog that all queries made by W are distinct.
Let C be a log-sparse candidate selector for L.Now, on input x 2f0; 1gn the machine M behaves
as follows:
runs W on input x. Each time W makes an oracle query q, the machine M provides a
response as follows:
1.1 If q 2 C then M responds with 0.1.2 Else it continues by trying in parallel both possible answers 0 and 1. That is, M branches
into two parallel" computations. In the rst it lets the response to q be 0 and in the
second it lets the response to q be 1. It then continues to run W in each computation.
In this manner M generates a number of parallel computations. After dnd steps all of these
computations have halted and each has yielded an nc bit output the output of W .
now examines the set of outputs from the previous step. It accepts if at least one of these
outputs w satis es x; w 1, and rejects otherwise.
This completes the description of the machine M. The fact that it works should be clear, but for
completeness let us spell it out.
First, to see that M accepts x if and only if x 2 L, it su ces to check that on at least one of
the parallel computations all oracle queries are correctly that is, according to L answered. But
Step 1.1 is obviously correct by de nition of the candidate selector and in step 1.2 everything
is being tried, so one of the runs will certainly end up having all the right query answers.
The next thing to check is that M runs in polynomial time. It su ces to show that the total
number of parallel computations is nO 1 .For this it su ces to show that the number of branches
on any path is O log n . Wenow argue the latter. First note that any query q has length at
most dnd the running time of W . But branching only occurs when q 2 C, and wehave assumed
that all W's queries are distinct. So the number of times branching occurs is at most the size of
dnd g, which is at most C dnd O logn . This completes the proof.
We can now put the pieces together to obtain the result:
Theorem 2.9 If EE NEE then there exists a language in NP for which search does not reduceto decision.
Proof: By Lemma 2.7 there exists a uniformly log-sparse language L 2 NP , P. By Lemma 2.8,
search cannot reduce to decision for L.
Note that the fact that search does not reduce to decision for L implies that L is not NP-complete.
The existence of a non NP-complete language in NP,P can however be established assuming only
.3 Deciders and their Properties
Before extending the ideas of the previous section to interactive proofs and checking, we pause to
develop some technical materiel. This materiel will be useful in proving the results of later sections.
In particular weintroduce the notion of a decider" which will enable us to give a uni ed and more
concise treatment of the rest of the results of this paper. We begin with the de nition.
De nition 3.1 Let D beaprobabilistic, polynomial time oracle machine. We say that D is a
decider for language L if for each x 2f0; 1g the following is true:
accepts with probability 2 3
then the probability that DA x accepts is 1 3 for all oracles A.We note that L has a decider if and only if it is in function-restricted IP cf. BK . So deciders
are just a wayofcharacterizing languages in frIP. They can also be viewed as checkers for yes
instances." They are weaker than multi-prover interactive proofs: the results of FRS imply that if
L has a decider then it has a multi-prover interactive proof. For us the motivation of De nition 3.1
is to generalize" the notion of a witness nder in the light of our proof of Lemma 2.8. The property
of the witness nder that was important in that proof was that it was correct for x 2 L as long
as oracle queries were answered correctly i.e. according to L , and it was correct" for x 2 L nomatter how oracle queries were answered. Like a witness nder, correctness of the decider on inputs
guaranteed except here only with high probability as long as oracle queries are correctly
answered. On the other hand if x 2 L then again correctness is guaranteed with high probability,no matter how oracle queries are answered.Aswe will see, these properties will su ce for us to
appropriately extend Lemma 2.8 to Lemma 4.3.
The error probabilityof13 in the above de nition is not always su cient. It is convenientto
also de ne the following.
De nition 3.2 Let D beaprobabilistic, polynomial time oracle machine. We say that D is a
strong decider for L if for each x 2f0; 1g the following is true:
accepts with probability 1 , 2,jxj
then the probability that DA x accepts is 2,jxj for all oracles A.Standard error-reduction, of course, says that strong deciders exist whenever deciders exist. For
completeness let us state this as a proposition and provide a sketch of the proof.
Proposition 3.3 If L has a decider then it has a strong decider.
Proof: Let D be a decider for L.We de ne machine D0 as follows. On input x, machine D0 runs D
on input x a total of m O n times, each time with independent coin tosses. The oracle queries
made by D0 are answered by D0 byway of his own oracle that is, if D makes oracle query q then
D0 makes oracle query q, and provides the answer he receives to D . D0 outputs the majorityvote
of the outputs of D in the m trials. To see that D0 is a strong decider for L, let X1A;:::;XmA denote
the sequence of random variables representing the outcomes of D with oracle A in these successive
trials. These are independent, and for each i 1;:::;msatisfy Pr XL 1 2 3 in the case that
oracles A in the case that x 2 L. An application of standard
Cherno bounds yields the desired conclusions.
Wesaw in Section 2 that reducing search to decision for uniformly log-sparse languages is hard.
Here we show that these same languages also do not have deciders unless they are in BPP.
Lemma 3.4 Suppose L is uniformly log-sparse and has a decider. Then L 2 BPP.
Proof: By Proposition 3.3, L has a strong decider D.We showhowtouseD to construct a BPP
machine M to decide L. The idea is very much the same as that in the proof of Lemma 2.8, with
the decider here playing the role that the witness nder played in that proof. That is, on input x
the machine M will run D on input x and answer its oracle queries according to the same rules
as those used in the proof of Lemma 2.8. M accepts if and only if the decider accepts on at least
one of the parallel computations. The main di erence with respect to Lemma 2.8 lies in the fact
that there is no way to tell whether a particular output of the decider is correct in Lemma 2.8
one can always check whether or not the output of the witness nder is really a witness . Instead,
the correctness of the procedure follows from the fact that the error probabilityofD is very small
2,n . Details follow.
Let d be a constant such that D always halts in dnd steps on inputs of length n. Let C be
the log-sparse candidate selector for L.We assume wlog that all oracle queries made by D are
distinct. On input x 2f0; 1gn the machine M behaves as follows:
runs D on input x. Each time D makes an oracle query q, the machine M provides a
response as follows:
1.1 If q 2 C then D responds with 0.1.2 Else it continues by trying in parallel both possible answers 0 and 1. That is, M branches
into two parallel" computations. In the rst it lets the response to q be 0 and in the
second it lets the response to q be 1. It then continues to run W in each computation.
In this manner M generates a number of parallel computations. After dnd steps all of these
computations have halted and each has yielded a output of 1 or 0 the output of D .
now examines the set of outputs from the previous step. It accepts if at least one of these
outputs is 1.
Since the answers in one of these parallel computations correspond to L, machine M accepts with
dnd g, and let Adenote the set of all subsets of Q. Each parallel computation of M corresponds to running D with
some oracle A 2A. It follows that the probability that M accepts is at most A2A Pr DA accepts .
By assumption D is a strong decider for L,sowe can bound this by jAj 2,n. But we claim that
so the probability that M accepts is completing the proof. To justify the
claim, note that jAj 2jQj and jQj C dnd O log n .
Recall that BPEE denote the class of languages accepted in time 2c2n for some constant c 0by
a probabilistic machine with bounded error. By an argument analogous to that used in the proof
of Lemma 2.7 we can show the following.
Lemma 3.5 If NEE BPEE then there exists a uniformly log-sparse language in NP , BPP.Combining this with Lemma 3.4 we obtain the following theorem whichwe will use in the next two
sections.
Theorem 3.6 If NEE BPEE then there exists a language in NP which does not have a decider.We remarked earlier that L has a decider i L 2 frIP, so Lemma 3.6 says that NEE BPEE impliesNP frIP. In later sections we will use Theorem 3.6 to show that NEE BPEE implies NP
Checkby showing that languages in compIP and Checkhave deciders cf. Lemmas 4.3
and 5.2 .
CompetitiveInteractive Proofs
We begin by recalling the notion of an interactive proof. We then de ne competitiveinteractive
proofs and present our results.
4.1 Interactive Proofs
Interactive proofs are extensions of NP ones, so let us begin by recalling the latter. An NP proof
system for a language L 2 NP is de ned by a polynomial time veri er V .We imagine this veri er
talking to a prover." The parties receive a common input x, and the prover's goal is to convince
the veri er to accept. To this end he is allowed to send the veri er a single message of length
. The veri er's decision as to whether or not to accept is made as a function of the common
input and this message since the veri er is deterministic, this decision" is a polynomial time
binary predicate evaluated on the common input and the prover's message . In the case that
exist some deterministic prover" P who can convince the veri er to accept
this is the completeness" condition .  In the case that x 2 L, no  prover" should be able toconvince the veri er to accept this is the soundness" condition . We usually specify an NP proof
system as a pair P;V where P is a prover satisfying the completeness condition. Clearly, L 2 NP
if and only if it possesses an NP proof system.
Interactive proofs, whichwere introduced by Goldwasser, Micali and Racko GMR , are a
natural extension of such NP proof systems. Both parties are now allowed to be probabilistic.
Moreover, they are allowed to interact that is, they exchange messages for a polynomial number
of rounds, and it is only at the end of this exchange that V decides whether or not to accept . We
say that P;V isaninteractive proof for a language L if 1 on common input a string in L,itis
possible for P to induce V to accept with high probability, and 2 on common input a string not
in L, there is no prover who can prevent V from rejecting with high probability.
Let us now proceed more formally. A party A in an interactive proof may be viewed as a
probabilistic function of the common input and the conversation so far. The outcome of this
function on input x the common input and c transcript of conversation so far , whichwe denote
by A x; c , is the next message computed by A and sent to the other party .y We assume that the
transcript of the conversation at any pointmay be uniquely parsed into its constituent messages.
Wemay discuss the complexity of such parties in the usual way, viewing them as being computed by
probabilistic Turing machines. For example, the veri er is a party computable by a probabilistic,
polynomial time TM. Complexity is measured as a function of the length of the common input
whichwe usually denote by n . The total numberofmoves a move consists of a party computing
and sending a message as well as the length of all messages are assumed to be bounded by
a polynomial in n. At the end of the interaction, the veri er accepts or rejects by applying a
deterministic binary predicate to the common input and transcript of conversation. Suppose
a prover A interacts with a veri er B on common input x. The probability that B accepts in
its interaction with A on common input x" is the probability that B accepts given the common
input x and transcript 1 1 ::: g,1 g,1 g chosen according to the following experiment: 1
Here g g n is the total number of moves, is the empty string, and we are assuming for
simplicity that A speaks rst and last. The probabilities are over the random choices of both
parties in this conversation .
De nition 4.1 Interactive Proofs GMR Let P;V beapair of probabilistic functions. We
say that P;V is an interactive proof system for language L if V is probabilistic, polynomial time,
and
1 For every x 2 L the probability that V accepts in its interaction with P on common input x is
2 For every x 2 L and every function Pb, the probability that V accepts in its interaction with Pbon common input x is 1 3.
The rst condition is the completeness condition and the second is the soundness condition.
We note the strength of the soundness condition: the quanti cation is over all functions Pb we call
them cheating" or   dishonest" provers , even non-computable ones.
We note that an NP proof system is a special kind of interactive proof system. Speci cally,an
NP proof system is an interactive proof system P;V in which both P and V are deterministic,
the interaction is restricted to a single message from the prover to the veri er, and the probabilities
in the completeness and soundness conditions are 1 and 0 rather than 2 3 and 1 3 , respectively.
The addition of interaction and randomness, however, seems to add signi cantly to the language
recognition power of the system. It was established by Lund, Fortnow, Karlo and Nisan LFKN
that IP the class of languages possessing interactive proofs of membership contains the polynomial
time hierarchy, and Shamir Sh extended this to show that IP equals PSPACE.
y When wesay that this function is probabilistic we mean that to any x; c party A actually associates a distribution
on strings, and A x;c is a random element of this distribution.
4.2 CompetitiveInteractive Proofs
A basic complexity theoretic question is to determine how e cient the prover P can be in an
interactive proof P;V of a language L. Certainly he would need at least the ability to decide
the language himself. We de ne a competitiveinteractive proof system as one where the prover is
allowed no more than this. Speci cally,hemust run in probabilistic polynomial time given access
to L as an oracle. As we will see, competitiveinteractive proofs represent the natural generalization
of the problem of decision vs. search.
De nition 4.2 Let P beaprobabilistic polynomial time oracle machine and V aprobabilistic
polynomial time machine. We say that P,V is a competitive interactive proof system for a language
1 For every x 2 L the probability that V accepts in its interaction with PL on common input x
is
2 For every x 2 L and every interactive TM Pb, the probability that V accepts in its interaction
6 with Pbon common input x is 1 3.
The rst condition is the completeness condition and the second is the soundness condition. We
call P a competitive prover.
We note that the soundness condition remains the same as in the de nition of interactive proofs. In
particular, we do not restrict the computational power of the cheating" prover Pbin the case x 2 L.Our goal is to understand the di culty of providing a correct proof, and unrestricted soundness
would appear to be an inherent property of proofs."
Competitive NP proof systems are de ned in the natural way. That is, a competitive NP
proof system is a competitiveinteractive proof system in which both parties are deterministic, the
interaction is restricted to a single message from the prover to the veri er, and the probabilities
in the completeness and soundness conditions are 1 and 0 rather than 2 3 and 1 3 , respectively.
Equivalently, it is an NP proof system in which the prover is restricted to polynomial time plus an
oracle for L.Wenow note that search reduces to decision for L if and only if L has a competitive
NP proof system the prover in the competitive NP proof system corresponds to the witness nder .
It is in this sense that competitiveinteractive proofs are the natural extension of the problem of
decision versus search.
4.3 A NP Language not Possessing a CompetitiveInteractive Proof
In Section 2 we presented a language L 2 NP for which search is unlikely to reduce to decision.
In other words, L is unlikely to have a competitive NP proof system. The truth, however, is that
proving membership in NP languages remains hard even when interaction and randomness are
allowed: we will show here that there is probably an NP language which does not even havea
competitiveinteractive proof system. Given the results of Section 3 we need only the following
lemma which shows that any language possessing a competitiveinteractive proof also has a decider
or, equivalently, that compIP frIP .
Lemma 4.3 Suppose L has a competitive interactive proof system. Then it has a decider.
Proof: Let P;V be a competitiveinteractive proof for L.We note that in probabilistic polynomial
time we can run both P and V . So given an oracle for A, the machine D, on input x, can sample
the space of conversations between PA and V on input x, and accept if and only if the conversation
obtained is accepting. Details follow.
Let r n denote a polynomial bound on the number of coin tosses used by P and V on any input
of length n. D picks, uniformly at random, a r n bit string RP and a r n bit string RV .He
now runs P and V on common input x, using RP as the coins for P and RV as the coins for V .
That is, assuming for example that P sends the rst message, D would run P with coins RP
to get P's rst message. He would then run V with coins RV to get the response, and so on.
Oracle queries made by P in this process are answered by D byway of its own oracle that is, if
makes oracle query q then D makes oracle query q, and provides the answer he receives to P .
Eventually D obtains the output of V 1 if V accepts and 0 otherwise , and outputs this value.
Given any particular oracle A, it is the case that DA x isa01 random variable, and clearly the
probability that it is 1 equals the probability that V accepts in its interaction with PA on common
input x. By the assumption that P;V was a competitiveinteractive proof for L it follows that
in the case that x 2 L, and Pr DA x 1 1 3 for all oracles A in the case
that x 2 L.Combining Lemma 4.3 and Theorem 3.6 yields the theorem.
Theorem 4.4 If NEE BPEE then there exists a language in NP that does not have a competitiveinteractive proof.
We note that wehave done more than simply show that interactive proofs may be more powerful
than competitive ones, because the language L of Theorem 4.4 is in NP, a subclass of IP which
possesses particularly simple interactive proofs. To show only that interactive proofs are more
powerful than competitive ones, it would su ce to present a language in IP but not necessarily
in NP which does not have a competitiveinteractive proof. This can be done under weaker
assumptions, by an extension of the same argumentwe used above. For example, let
Then we can show that if EESPACE BPEE then there exists a language in IP whichdoesnotpossess a competitiveinteractive proof.
In general, to construct a language L which lies in some particular complexity class C but
does not possess a competitiveinteractive proof, it su ces to assume that the double-exponential
counterpart" of C is not contained in BPEE. We put the phrase   double-exponential counterpart"
in quotes because it, of course, does not always make sense many classes have no such counterpart .
But there are many natural classes such as those used here for which this paradigm does make
sense.
4.4 Zero-Knowledge Aspects
The competitive" aspects of zero-knowledge proofs may also be worth investigating. To initiate
suchaninvestigation, let us try to discuss brie y what one can easily infer from known work and
what are the open questions.
Do NP languages have competitive zero-knowledge interactive proofs? In general, of course,
they probably do not since by Theorem 4.4 they probably do not even have competitiveinteractive
proofs let alone ZK ones . An appropriate question then is whether NP languages which possess
competitiveinteractive proofs also possess competitive zero-knowledge interactive proofs. The
answer depends on the kind of zero-knowledge one considers and on the kind of cryptographic
assumptions one is willing to make.
Let us rst consider computational ZK. The result of Goldreich, Micali and Wigderson GMW
implies that NP-complete languages have competitiveZKinteractive proofs, given the existence of
one-way functions more generally, it implies that if search reduces to decision for L then L has
a competitiveZKinteractive proof, given the existence of one-way functions . We do not know
whether the assumption that there exist one-way functions su ces to show that any language which
possesses a competitiveinteractive proof also possesses a competitiveZKinteractive proof. But
wedoknow that the latter conclusion may be established with stronger assumptions suchasthe
existence of ideal" secure circuit evaluation or the existence of  oblivious transfer." This follows
from the result of Kilian Ki and we refer the reader to that paper for details on what exactly are
these assumptions .
All statistical ZK languages known to possess competitiveinteractive proofs are also known
to possess statistical ZK competitiveinteractive proofs these languages are graph isomorphism
GMW , graph non-isomorphism GMW , and quadratic non-residuosity GMR . We do not, of
course, know whether or not quadratic-residuosity has a competitive statistical ZK interactive proof
given that we do not know whether or not it has a competitiveinteractive proof at all.
5 Program Checking
Blum and Kannan BK introduced the notion of program checkers. Informally,achecker for a
function f is a probabilistic, polynomial time oracle machine which receives as an oracle a program
which purports to compute f. The checker also receives an input x. If the program is entirely
correct that is, P y f y for all y then the checker is supposed to accept with high probability.
However if the program disagrees with f on the particular input x provided to the checker then the
checker should reject with high probability. The de nition follows. We note that by a program"
we mean a deterministic machine that halts on all inputs. We also recall that the characteristic
function of a language L is the function L: f0; 1g f0; 1g de ned by L x 1ifx 2 L and 0
otherwise.
De nition 5.1 BK Let C beaprobabilistic polynomial time oracle TM. C is a checker for
f: f0; 1g f0; 1g if for all programs P and all x 2f0; 1g it is the case that
accepts with probability 2 3
then the probability that CP x accepts is 1 3.We say C is a checker for a language L if it is a checker for the characteristic function of L. L is
checkable if it has a checker.
The de nition is close in spirit to that of competitive interactive proofs, but there are two important
di erences. First, unlikeinteractive proofs, checking is a symmetric" notion in which the
checker for language L must be able to determine that P is correct on x not only when x 2 L but
also when x 2 L. Second, programs are history independent objects, while cheating provers arenot. Thus, if L and L both have competitiveinteractive proofs then L has a checker, while wedo
not know whether or not every checkable language has a competitiveinteractive proof.
Checkers are also related to multi-prover interactive proofs BGKW . In particular, results of
FRS imply that the class of languages which possess checkers in contained in MIP coMIP where
MIP is the class of languages possessing multi-prover interactive proofs of membership . We note
that MIP NEXP, by the result of BFL .
Blum and Kannan BK showed that Check frIP cofrIP. It follows that checkable languages
have deciders. For completeness, however, let us see this directly.
Lemma 5.2 Suppose L has a checker. Then it has a decider.
Proof: Let C beachecker for L. Let D be the probabilistic polynomial time oracle machine
which, on input x,works as follows. D begins by querying its oracle with the string x. If the oracle
returns 0 then D rejects. Else, it runs C on input x, using its own oracle denoted A to answer C's
oracle queries, and accepts i C accepts. We claim that D is a decider for L.To see this we need
to check that for each x 2f0; 1g the two conditions of De nition 3.1 hold. The rst condition is
clear. To see that the second is true, suppose x 2 L, and suppose rst that A x 0. In this case,D rejects with probability1.Now suppose A x 1. Then the probability that D accepts is at
most 1 3 because C isachecker.
Combining Lemma 5.2 and Theorem 3.6 yields the theorem.
Theorem 5.3 If NEE BPEE then there exists a language in NP that is not checkable.Similarly if EESPACE BPEE then there exists a language in PSPACE which is not checkable.We recall that a language L is coherent if the membership of x in L can be decided in probabilistic
polynomial time and bounded error by a machine called the examiner which has access to L
as an oracle but is allowed to query this oracle only on points di erent from x.IfL is not coherent
wesay it is incoherent. Previous negative results on checking were established by rst exhibiting
incoherent sets and then exploiting Yao's observation that any incoherent set is uncheckable cf.
Ya, BF . We note that our stronger results are obtained more directly. Moreover, our techniques
indicate that even within NP the class of coherent sets could be much larger" than the class of
checkable ones. Let us sketchwhy this is so.
The disjoint union" of languages A and B, denoted A B,isf0x
construct is widely used in complexity theory eg. BD, HH . It is easy to see cf. BF that L L is
coherent for any language L. It is also easy to see that the transformation L L L preserves manycomplexitycharacteristics of L; for example, membership in NP; compNP; compIP; Check; frIP. In
particular, combining this observation with Theorem 5.3 yields the claimed separation:
Theorem 5.4 If NEE BPEE then there exists a language in NP that is coherent but not checkable

6 Towards Competitive Proofs for Quadratic Residuosity
In this section we return to the unresolved question of whether the language of quadratic residuosity
has a competitiveinteractive proof system, and present a special case of the problem where
competitive proofs are possible.
6.1 De nitions
We will be looking at promise" problems rather than problems of language membership. The
di erence is that in the former we begin with a promise" that the input already belongs to some
set, and wehave only to decide" whether or not it falls in a given subset of this set. Such problems
have been considered in manyworks; eg. ESY . The formalization we use is di erent from but
equivalent to the ones used in these works, and is as follows. The problem is speci ed by a pair of
disjoint sets A; B . Intuitively, the input is promised to be in A B and wehave to decide whether
it is in A or in B. Corresponding to promise problems are promise oracles which are guaranteed to
be correct only when the promise" is true.
De nition 6.1 A promise problem isapair of disjoint sets A; B .Apromise oracle for a promise
problem which given a query q returns 1 if q 2 A and 0 if q 2 B.
Note that while promise problems are, intuitively, easier" than language recognition problems,
promise oracles are correspondingly weaker than normal oracles. In particular, a promise oracle
for than an oracle for just A or B in that its response on queries outside A B
is indeterminate.
A competitiveinteractive proof for a promise problem A; B is just an interactive proof that
given that x 2 A B and having the property that the competitive" prover gets only a
promise oracle for A; B . The more formal de nition follows.
De nition 6.2 Let P beaprobabilistic polynomial time oracle machine and V aprobabilistic
polynomial time machine. We say that P;V is a competitive interactive proof for promise problem
1 For every x 2 A and every promise oracle O for A; B , the probability that V accepts in its
interaction with PO on common input x is 2 3
2 For every x 2 B and every interactive TM Pb, the probability that V accepts in its interaction
with Pbon common input x is 1 3.
6.2 Results
We recall that x 2 Z is a quadratic residue or square modN if x y2 mod N for some
and a quadratic non-residue or non-square modN otherwise. Also, recall from Section 1.2
that
QR f x; N :x is a square mod N g
QNR f x; N :x is a non-square mod N
The special case we are interested in is when N is the product of a constantnumber of distinct odd
primes. To be more precise, rst de ne
is a product of s distinct odd primes g
is a product of s distinct odd primes
We will present a competitiveinteractive proof that x; N 2 QRs given that it is already in
QRs QNRs. Note that QRs and QNRs are not complements of each other so that, formally,we
are talking of a competitiveinteractive proof for the promise problem QRs; QNRs in the sense of
De nition 6.2.
Theorem 6.3 Let s be an integer 1. Then the promise problem QRs; QNRs possesses a competitive
interactive proof.
In related work, Kompella and Adleman KA presentcheckers for this same special case of quadratic
residuosity when the modulus is the product of a constantnumber of primes i.e. they present
checkers for the promise problem QRs; QNRs . Their construction does not, however, extend to
competitiveinteractive proofs, because the correctness of their checker uses the fact that a program
in contrast to a cheating prover is history independent.
To prove Theorem 6.3,we begin by recalling some basic number theoretic facts. We refer the
reader to An, NZ for number-theoretic background and justi cation of these facts.
For x 2 ZN we let QN x 0ifx is a quadratic residue mod N, and 1 otherwise. Suppose
ps where p1;:::;ps are distinct odd primes. De ne the binary relation ' on ZN by
This is an equivalence relation. The equivalence class of x under this relation namely f y 2
is called its residue class. The product xy mod N of two elements
square mod N if x; y are from the same residue class and a non-square mod N otherwise. The
total number of residue classes is 2s, and they are all of the same size. We will denote them by
;:::;R2s, with the convention that the last, R2s, is the class of quadratic residues mod N.
We recall that there exists a competitiveinteractive proof for quadratic non-residuosity.We
will exploit this fact by reducing the proof of x; N 2 QRs to a polynomial number of proofs of
non-residuosity in suchaway that the prover need use only probabilistic, polynomial time and a
promise oracle for QRs; QNRs . The rst step is the following de nition.
De nition 6.4 Let N beaproduct of s distinct odd primes and let t 2s. We calavector
representative of ZN if the following conditions hold
1 yi is a non-squaremod N for each i 1;:::;t, 1
is a non-squaremod N for each pair of indices
This leads us to a way to reduce a residuosity test to to a collection of non-residuosity tests as long
as we are in possession of a representativevector.
Proposition 6.5 Let N beaproduct of s distinct odd primes and let x 2 Z . Suppose y
y1;:::;yt,1 is representative of ZN where t 2s . Then x; N 2 QRs if and only if xyi mod N
is a non-squaremod N for each i 1;:::;t, 1.
Proof: xyi mod N will be a non-square mod N for each i 1;:::;t, 1 if and only if its residue
class di ers from the residue class of yi for each i 1;:::;t, 1. But since y is representative, this
happens if and only if x is a square mod N.
To use this, however, wehave to be able to get representativevectors. It su ces to showhow
the prover can construct a representativevector and then convince the veri er that it is indeed
representative, all using only probabilistic, polynomial time and a promise oracle for QRs; QNRs .
Proposition 6.6 Thereisaprobabilistic, polynomial time oracle machine R which on input x; N 2
QRs QNRs and access to the promise oracle for QRs; QNRs outputs either a representative vector
for Z or the special symbol ?, with the probability of the latter event being at most 1 4.
Proof: R picks at random y1;:::;ym 2 ZN t,1, where t 2s and m is a constant to be de ned
later. For each i 1;:::;mthe machine R then uses the promise oracle to test whether or not the
conditions of De nition 6.4 hold for yi. If some vector yi passes the test then the rst suchvector is
output If all vectors fail the test then R outputs ?. The probability that a particular vector passes
the test is t , 1 tt,1, which is a positive constant. So it su ces to choose m to be a constant
such that
A crude calculation shows that m O 2e t su ces . That R runs in probabilistic, polynomial
time is clear.
We can now proceed to describe the protocols. We begin by recalling following GMR the basic
competitive protocol to prove non-residuosity.
Protocol QNR
Input: x; N and 1k
picks at random c1;:::;ck 2f0; 1g and r1;:::;rk 2 ZN , sets zi xciri2 mod N for
sends z1;:::;zk to P.
P1 P sets di to 0 if zi is a quadratic residue mod N and 1 otherwise for i 1;:::;k , and sends
d1;:::;dk to V .
accepts if and only if ci di for all i 1;:::;k.
Proposition 6.7 Protocol QNR has the following properties:
then the probability that V accepts in its interaction with P is 1
2 If x; N 2 QNR then for any Pb the probability that V accepts in its interaction with Pb is
6 ,k
.
3 P is competitive that is, it runs in probabilistic, polynomial time given an oracle for QNR .
Proof: The rst two items follow from basic properties of modular residues, and we refer the
reader to GMR for proofs. The last item is clear.
Wenow proceed to the competitiveinteractive proof for QRs.We will use Protocol QNR as a
subprotocol.
Input:
Notation: We let t 2s.
runs the algorithm of Proposition 6.6 and sends the output to V
receives ? from P then it rejects. If instead it receives a vector y y1;:::;yt,1 2
Z t,1 then the parties proceed to the next step.
Sub-Protocol: P uses Protocol QNR with security parameter k set to 2 to provetoV
that
1 yi is a non-square mod N for each i 1;:::;t, 1
is a non-square mod N for each pair of indices
3 xyi mod N is a non-square mod N for each i 1;:::;t, 1
a total of t , 1 t +2 2invocations of the QNR protocol .
accepts i each of the above sub-proofs was accepting.
The correctness of the protocol follows from the results established above. Details follow.
Suppose QRs. Proposition 6.6 implies that the parties get a representativevector
and proceed to the sub-protocol with probability 3 4. De nition 6.4 and Proposition 6.5 imply
that the inputs to the non-residuosity sub-proofs are all indeed non-squares mod N, and thus
Proposition 6.7 implies that these sub-proofs all succeed with probability1. SoV accepts with
Suppose QNRs.IfPbsends ? in its rst step then V rejects, so suppose he sends a
vector y y1;:::;yt,1 2 ZN t,1.Ify is not representative then by De nition 6.4 either there
is an i such that yi is a square mod N or there is a pair i jsuch that yiyj mod N is a square
mod N. In either case, the corresponding non-residuosity sub-proof fails with probability 3 4,
and V rejects. So suppose y is representative. But then Proposition 6.5 implies there is an i such
that xyi mod N is a square mod N. So the corresponding non-residuosity sub-proof fails with
probability 3 4 and V again rejects.
The competitiveness of P follows from Propositions 6.6 and 6.7.
The reason this does not extend to arbitrary N is, of course, that the number of residue classes
could in general be exponential in the length of N, and in polynomial time we could not even write
down a representative list. On the other hand, working through the proofs shows that the result
does extend to the case where s: N N is a polynomial time computable function of N whichis
bounded abovebylglglgN lglgjNj.For simplicitywehave stuck to the case of constant s.
Clearly, the weakness of this result is in the promise" that N is already a product of exactly s
odd primes; this is what may be hard to prove competitively if one wants a competitiveinteractive
proof of QR.
7 Open Questions
Quadratic-residuosity.We think that the most interesting open question is whether or not the
language of quadratic residuosity has a competitiveinteractive proof. Conditional results on the
subject would also be interesting: for example, could one show that if quadratic residuosity has
a competitiveinteractive proof then factoring is reducible in probabilistic, polynomial time
to deciding quadratic residuosity? Note that an a rmative answer to this last question would
imply that if QR has a competitiveinteractive proof then it has an NP-proof via the simple
factorization witness."
Reducing assumptions. Another open question is whether one can reduce the assumptions
required for our results. In particular can one show that there is a language for which search
does not reduce to decision given P NP, or even E NE? Or could cryptographic assumptions
such as the existence of one-way functions be used to establish the existence of languages in IP
which don't have competitiveinteractive proofs?
Other settings. What is the relationship of decision to search in the context of optimization
problems and approximation algorithms, and does search reduce to decision" in this setting?
For example, consider the Traveling Salesman Problem TSP . Let G denote the weightof
an optimal tour on a weighted graph G, and suppose 1 is a constant. Suppose A is an
oracle satisfying G A G G for all graphs G. Is there a polynomial time procedure
which, with oracle access to A and input G, outputs a tour in G ofweight at most G ?
Perfect completeness.Aninteractive proof P;V for L is said to have perfect completeness if
the probability of acceptance in the completeness condition is 1. We know that any language
L possessing an interactive proof also possesses one with perfect completeness FGMSZ . Does
any language possessing a competitiveinteractive proof also possesses a competitiveinteractive
proof with perfect completeness? One of the motivations for this question is the fact that
our competitive proof for the special case of quadratic residuosity in Section 6 does not possess
perfect completeness .
Zero-knowledge.We discussed the open questions in Section 4.4.

Acknowledgments

Many people pointed out to us the error in HSI : we thank Eric Allender, Juris Hartmanis, Jack
Lutz, and OsamuWatanabe in this regard. We thank Muli Safra, Lance Fortnow and Jack Lutz
for helpful discussions, and Silvio Micali for suggesting the term competitiveinteractive proofs."
We thank Oded Goldreich for many helpful comments on the paper. We thank Satish Thate for
drawing our attention to the results of La mentioned in Section 2. Finally we thank a pair of
anonymous referees for manyvaluable comments on the paper.


--R

Lecture Notes on the Complexity of Some Problems in Number Theory.
Limitations of the Upward Separation Technique.

Languages that are Easier than their Proofs.
Improved Bounds on Coherence and Checkability.
The Complexity of Decision versus Search.
Making Zero-Knowledge Provers E cient
On the Theory of Average Case Complexity.
Multiprover Interactive Proof Systems: How to RemoveIntractability Assumptions.
Designing Programs that Check their Work.
Some Comments on Functional Self-Reducibility and the NP Hierarchy

The Complexity of Promise Problems with Applications to Public-Key Cryptography
On the Power of Multiprover Interactive Protocols.
On Completeness and Soundness in Interactive Proof Systems.
The Knowledge ComplexityofInter- active Proofs
Complexity Classes without Machines.
Sparse Sets in NP-P: EXPTIME versus NEXPTIME

Private communication
Decision Versus Search Problems in Super-Polynomial Time
The ComplexityofParallel Search.
Achieving Zero-Knowledge Robustly
Fast Checkers for Cryptography.
Personal communication.
On the Structure of Polynomial Time Reducibility.
Algebraic Methods for Interactive Proof Systems.
AnIntroduction to the theory of Numbers.
Natural Self-Reducible Sets
IP PSPACE.
Private communication via Beigel and Feigenbaum
On the Relative Complexity of Checking and Evaluating.

--TR

--CTR
Salil Vadhan, On transformation of interactive proofs that preserve the prover's complexity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.200-207, May 21-23, 2000, Portland, Oregon, United States
Minh-Huyen Nguyen , Salil Vadhan, Zero knowledge with efficient provers, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
Liming Cai , David Juedes, On the existence of subexponential parameterized algorithms, Journal of Computer and System Sciences, v.67 n.4, p.789-807, December
sparse sets;interactive proofs;quadratic residuosity;NP-completeness;program checking;self-reducibility