Randomness is Hard.
We study the set of incompressible strings for various resource bounded versions of Kolmogorov complexity. The resource bounded versions of Kolmogorov complexity we study are polynomial time CD complexity defined by Sipser, the nondeterministic variant CND due to Buhrman and Fortnow, and the polynomial space bounded Kolmogorov complexity CS introduced by Hartmanis. For all of these measures we define the set of random strings $\mathrm{R}^{\mathit{CD}}_t$, $\mathrm{R}^{\mathit{CND}}_t$, and $\mathrm{R}^{\mathit{CS}}_t$ as the set of strings $x$ such that $\mathit{CD}^t(x)$, $\mathit{CND}^t(x)$, and $\mathit{CS}^s(x)$ is greater than or equal to the length of $x$ for $s$ and $t$ polynomials. We show the following:   $\mathrm{MA} \subseteq \mathrm{NP}^{\mathrm{R}^{\mathit{CD}}_t}$, where $\mathrm{MA}$ is the class of Merlin--Arthur games defined by Babai. $\mathrm{AM} \subseteq \mathrm{NP}^{\mathrm{R}^{\mathit{CND}}_t}$, where $\mathrm{AM}$ is the class of Arthur--Merlin games.  $\mathrm{PSPACE} \subseteq \mathrm{NP}^{\mathrm{cR}^{\mathit{CS}}_s}$.  In the last item $\mathrm{cR}^{\mathit{CS}}_s$ is the set of pairs $\langle x,y \rangle$ so that x is random given y. These results show that the set of random strings for various resource bounds is hard for complexity classes under  nondeterministic reductions.This paper contrasts the earlier work of Buhrman and Mayordomo where they show that for polynomial time  deterministic reductions the set of exponential time Kolmogorov random strings is not complete for EXP.
Introduction
The holy grail of complexity theory is the separation of complexity classes
like P, NP and PSPACE. It is well known that all of these classes possess
complete sets and that it is thus sucient for a separation to show that a
complete set of one class is not contained in the other. Therefore lots of
eort was put into the study of complete sets. (See [BT98].)
Kolmogorov [Lev94] however suggested to focus attention on sets which
are not complete. His intuition was that complete sets possess a lot of
\structure" that hinders a possible lower bound proof. He suggested to look
at the set of time bounded Kolmogorov random strings. In this paper we
will continue this line of research and study variants of this set.
Kolmogorov complexity measures the \amount" of regularity in a string.
Informally the Kolmogorov complexity of a string x, denoted as C(x), is the
size of the smallest program that prints x and then stops. For any string x,
C(x) is less than or equal to the length of x (up to some additive constant).
Those strings for which it holds that C(x) is greater than or equal to the
length of x are called incompressible or random. A simple counting argument
shows that random strings exist.
In the sixties, when the theory of Kolmogorov complexity was developed,
Martin [Mar66] showed that the coRE set of Kolmogorov random strings is
complete with respect to (resource unbounded) Turing reductions. Kummer
[Kum96] has shown that this can be strengthened to show that this set
is also truth-table complete.
The resource bounded version of the random strings was rst studied by
Ko [Ko91]. The polynomial time bounded Kolmogorov complexity C p (x),
for p a polynomial is the smallest program that prints x in p(jxj) steps
([Har83]). Ko showed that there exists an oracle such that the set of random
strings with respect to this time bounded Kolmogorov complexity is
complete for coNP under strong nondeterministic polynomial time reduc-
tions. He also constructed an oracle where this set is not complete for coNP
under deterministic polynomial time Turing reductions.
Buhrman and Mayordomo [BM95] considered the exponential time Kolmogorov
random strings. The exponential time Kolmogorov complexity
is the smallest program that prints x in t(jxj) steps for functions
. They showed that the set of t(n) random strings is not deterministic
polynomial time Turing hard for EXP. They showed that the class
of sets that reduce to this set has p measure 0 and hence that this set is not
even weakly hard for EXP.
The results in this paper contrast those from Buhrman and Mayordomo.
We show that the set of random strings is hard for various complexity classes
under nondeterministic polynomial time reductions.
We consider three well studied measures of Kolmogorov complexity that
lie in between C p (x) and C t (x) for p a polynomial and
. We
consider the distinguishing complexity as introduced by Sipser [Sip83]. The
distinguishing complexity, CD t (x), is the size of the smallest program that
runs in time t(n) and accepts x and nothing else. We show that the set
of random strings R CD
xed polynomial is
hard for MA under nondeterministic reductions. MA is the class of Merlin-
Arthur games introduced by Babai [Bab85]. As an immediate consequence
we obtain that BPP and NP BPP are in NP R CD
t .
Next we shift our attention to the nondeterministic distinguishing complexity
which is dened as the size of the smallest nondeterministic
algorithm that runs in time t(n) and accepts only x. We dene
R CND
xed polynomial. We show that
AM  NP R CND
t where AM is the class of Arthur-Merlin games [Bab85].
It follows that the complement of the graph isomorphism problem, GI, is
in NP R CND
t and that if for some polynomial t, R CND
The s(n) space bounded Kolmogorov complexity, CS s (xjy) is dened as
the size of the smallest program that prints x, given y and uses at most s(jxj+
tape cells [Har83]. Likewise we dene cR CS
for s(n) a polynomial. We show that PSPACE  NP cR CS
s .
For the rst two results we use the oblivious sampler construction of
Zuckerman [Zuc96], a lemma [BF97] that measures the size of sets in terms
of CD complexity, and we prove a Lemma that shows that the rst bits of
a random string are in a sense more random than the whole string. For
the last result we make use of the interactive protocol [LFKN92, Sha92] for
QBF.
To show optimality of our results for relativizing techniques, we construct
an oracle world where our rst result can not be improved to deterministic
reductions. We show that there is an oracle such that BPP 6 P R CD
t for
any polynomial t. The construction of the oracle is an extension of the
techniques developed by Beigel, Buhrman and Fortnow [BBF98].
Denitions and Notations
We assume the reader familiar with standard notions in complexity theory as
can be found e.g., in [BDG88]. Strings are elements of   , where
For a string s and integers n; m  jsj we use the notation s[n::m] for the
string consisting of the nth through mth bit of s. We use  for the empty
string. We also need the notion of an oblivious sampler from [Zuc96].
Denition 2.1 A universal (r; d; m; ;
)-oblivious sampler is a deterministic
algorithm which on input a uniformly random r-bit string outputs a
sequence of points z any collection of d
functions it is the case that
Pr
d
(Where
In our application of this denition, we will always use a single function
f .
Fix a universal Turing machine U , and a nondeterministic universal machine
U n . All our results are independent of the particular choice of universal
machine. For the denition of Kolmogorov complexity we need the fact that
the universal machine can, on input p; y halt and output a string x. For
the denition of distinguishing complexity below we need the fact that the
universal machine on input p; x; y can either accept or reject. We also need
resource bounded versions of this property.
We dene the Kolmogorov complexity function C(xjy) (see [LV97]) by
xg. We dene unconditional Kolmogorov
complexity by Hartmanis dened a time bounded version
of Kolmogorov complexity in [Har83], but resource bounded versions
of Kolmogorov complexity date back as far as [Bar68]. (See also [LV97].)
Sipser [Sip83] dened the distinguishing complexity CD t .
We will need the following versions of resource bounded Kolmogorov
complexity and distinguishing complexity.
uses at most
. (See [Har83].)
(1) U(p; x; y) accepts
rejects
runs in at most
(See [Sip83].)
(1) U n (p; x; y) accepts
rejects
runs in at most
(See [BF97].)
For 0 <   1 we dene the following sets of strings of \maximal" CD p
and CND p complexity.
Note that for these sets are the sets mentioned in the introduction. In
this case we will omit the  and use R CD
t and R CND
t . We also dene the set
of strings of maximal space bounded complexity.
cR CS
The c in the notation is to emphasize that randomness is conditional.
Also, cR CS
s technically is a set of pairs rather than a set of strings. The
unconditional space bounded random strings would be
R CS
s g:
We have no theorems concerning this set.
The C-complexity of a string is always upperbounded by its length plus
some constant depending only on the choice of the universal machine. The
CD- and CND-complexity of a string are always upperbounded by the C-
complexity of that string plus some constant depending again only on the
particular choice of universal machine. All quantiers used in this paper are
polynomially bounded. Often the particular polynomial is not important
for the sequel or it is clear from the context and is omitted. Sometimes we
need explicit bounds. Then the particular bound is given as a superscript to
the quantier. E.g., we use 9 m y to denote \There exists a y with jyj  m,"
or 8 =n x to denote \For all x of length n."
The classes MA and AM are dened as follows.
Denition 2.2 L 2 MA i there exists a jxj c time bounded machine M
such
1. x 2 L =) 9yPr[M(x;
2.
where r is chosen uniformly at random in f0; 1g jxj c
there exists a jxj c time bounded machine M such that
1. x 2 L =) Pr[9yM(x;
2.
where r is chosen uniformly at random in f0; 1g jxj c
It is known that NP [ BPP  MA  AM  PSPACE [Bab85].
Let #M(x) represent the number of accepting computations of a non-deterministic
Turing machine M on input x. A language L is in P if there
exists a polynomial time bounded nondeterministic Turing machine M such
that for all x:
Let g be any function. We say that advice function f is g-bounded if for
all n it holds that jf(n)j  g(n). In this paper we will only be interested in
functions g that are polynomial.
The notation  sn
T is used for strong nondeterministic Turing reductions,
which are dened by A  sn
Distinguishing Complexity for Derandomization
In this section we prove hardness of R CD
t and R CND
t for Arthur-Merlin and
Merlin-Arthur games respectively under NP-reductions.
Theorem 3.1 For any t with t(n) 2 !(n log n), MA  NP R CD
t .
and
Theorem 3.2 For any t with t(n) 2 !(n), AM  NP R CND
t .
The proof of both theorems is roughly as follows. First guess a string
of high CD poly -complexity, respectively CND poly -complexity. Next, we use
the nondeterministic reductions once more to play the role of Merlin, and
use the random string to derandomize Arthur. Note that this is not as
straightforward as it might look. The randomness used by Arthur in interactive
protocols is used for hiding and can in general not be substituted by
computational randomness.
The idea of using strings of high CD-complexity and Zuckerman's sampler
derandomization stems from [BF00] (Section 8), which is the full version
of [BF97]. Though they do not explicitly dene the set R CD
t , they use the
same approach to derandomize BPP computations there.
The proof needs a string of high CD p respectively CND p complexity for
some polynomial. We rst show that we can nondeterministically extract
such a string from a longer string with high CD t complexity (respectively
CND t complexity) for any xed t with t(n) 2 !(n log n).
Lemma 3.3 Let f be such that f(n) < n, and let t, t 0 and T be such
that T
all suciently large s with CD t holds that CD t 0
Proof . Suppose for a contradiction that for any constant d 0 and innitely
many s with CD t holds that CD t 0
log jf(jsj)j d 0 . Then for any such s there exists a program p s that runs in
recognizes only s[1::f(jsj)] where jp s j < (f(jsj) 2 log jf(jsj)j
d 0 . The following program then recognizes s and no other string.
Input y
Check that the rst f(jsj) bits of y equal using p s . (Assume
jf(jsj)j is stored in the program for a cost of log jf(jsj)j bits.)
Check that the last jsj f(jsj) bits of y equal
bits are also stored in the program.)
This program runs in time T Therefore it
takes at most t(jsj) steps on U for all suciently large s [HS66]. We lose the
log n factor here because our algorithm must run on a xed machine and
the simulation is deterministic.
The program's length is jp
log jf(jsj)j d which is less than jsj for
almost all s. Hence CD t (s) < jsj, which contradicts the assumption. 2
Corollary 3.4 For every polynomial n c , t 2 !(n log n) and suciently large
string s with CD t
c and s
Proof . Take t 0
c and apply Lemma 3.3. 2
Lemma 3.3 and Corollary 3.4 have the following nondeterministic analogon

Lemma 3.5 For every polynomial n c , t 2 !(n) and suciently large string
s with CND t
c and s
Proof . The same proof applies, with a lemma similar to Lemma 3.3. How-
ever, in the nondeterministic case the simulation costs only linear time [BGW70].Before we can proceed with the proof of the theorems, we also need some
earlier results. We rst need the following Theorem from Zuckerman:
Theorem 3.6 ([Zuc96]) There is a constant c such that for
(m) and
there exists a universal (r; d; m; ;
)-oblivious sampler which runs in polynomial
time and uses only
bits and outputs
We also need the following lemma by Buhrman and Fortnow:
Lemma 3.7 ([BF97]) Let A be a set in P. For each string x 2 A =n it
holds that CD p (x)  2 log(jjA =n jj) +O(log n) for some polynomial p.
As noted in [BF97], an analogous lemma holds for CND p and NP.
Lemma 3.8 ([BF97]) Let A be a set in NP. For each string x 2 A =n it
holds that CND p (x)  2 log(jjA =n jj) +O(log n) for some polynomial p.
From these results we can prove the theorems. If we, for Theorem 3.1, want
to prove that an NP machine oracle with oracle R CD
t can recognize a set A
in MA then the positive side of the proof is easy if x in A then there exists a
machine M and a string y such that a 2=3 fraction of the strings r of length
jxj c makes M(x; accept. So an NP machine can certainly guess one such
pair x; y as a \proof" for x 2 A. The negative side is harder. We will show
that if
2 A and we substitute for r a string of high enough CD complexity
(CND complexity for Theorem 3.2) then no y can make M(x; accept.
To grasp the intuition behind the proof let us look at the much simplied
example of a BPP machine M having a 1=3 error probability on input x and
a string r of maximal unbounded Kolmogorov complexity. There are 2 jxj k
possible computations on input x, where jxj k is the runtime of M . Suppose
that M must accept x then at most a 1=3 fraction, i.e. at most 2 jxj c
of these computations reject x. Each rejecting computation consists of a
deterministic part described by M and x and a set of jxj c coin
ips.
such a set of coin
ips with a binary string and we have that each rejecting
computation uniquely identies a string of length jxj c . Call this set B.
We would like to show by contradiction that a random string cannot be a
member of this set, and hence that any random string, used as a sequence of
coin
ips, leads to a correct result. Any string in B is described by M , x and
an index in B, which has length log jjBjj  jxj c log 3. So far there are no
grounds for a contradiction since a description consisting of these elements
can have length greater than jxj c . However we can amplify the computation
of M on input x by repetition and taking majority. Then, repeating the
computation x times, blows up the number of incorrect computations to
using x c+1 random bits. However, for large enough x a
description of jxj plus or minus some additive constant
depending on the the denition of Kolmogorov complexity used is smaller
then jxj c+1 and thus will lead to a contradiction.
Unfortunately, in our case the situation is a bit more complicated. The
factor 2 in Lemma 3.7 renders standard amplifaction of randomized computation
useless. Fortunately, Theorem 3.6 allows for a dierent type of
amplication using much less random bits, so that the same type of argument
can be used. We will now proceed to show how to t the amplication
given by Theorem 3.6 to our situation.
Lemma 3.9
1. Let L be a language in MA. For any constant k and any constant 0 <
1there exists a deterministic polynomial time bounded machine
M such that:
and r is chosen uniformly at random from the
strings in f0; 1g (1+)(1+k)m
2. Let L be a language in AM. For any constant k and any constant 0 <
there exists a deterministic polynomial time bounded machine
M such that:
(a) x 2 L =) Pr[9yM(x;
and r is chosen uniformly at random from the
strings in f0; 1g (1+)(1+k)m
Proof .
1. Furer et al. showed that the fraction 2=3 (see Denition 2.2) can be
replaced by 1 in [FGM + 89]. Now let ML be the deterministic polynomial
time machine corresponding to L in Denition 2.2, adapted so
that it can accept with probability 1 if x 2 L. Assume ML runs in
This means that for ML the 9y and 8y in
the denition can be assumed to be 9 n c y and 8 n c y respectively. Also,
the random string may be assumed to be drawn uniformly at random
from f0; 1g n c .
To obtain the value 2 km in the second item, we use Theorem 3.6 with
1=6. For given x and y let f xy be the FP function
that on input z computes ML (x;
We use the oblivious sampler to get a good estimate
for Ef xy . That is, we feed a random string of length (1+)(1+k)m in
the oblivious sampler and it returns sample points
z d on which we compute 1
d
is the machine
that computes this sum on input x, y and r and accepts i its value
is greater than 1=2.
If x 2 L there is a y such that Pr[ML (x;
no matter which sample points are returned by
the oblivious sampler. If
y. With
probability 1
the sample points returned by the oblivious sampler
are such that
d
, so 1
d
probability  2 km . 2
2. The proof is analogous to the proof of Part 1. We just explain the
dierences. For the 1 in the rst item of the claim we can again refer
to [FGM + 89], but now to Theorem 2(ii) of that paper. In this part
ML is the deterministic polynomial time machine corresponding to
the AM-language L and we dene the function f x : f0; 1g m 7! [0; 1] as
the function that on input z computes 9 n c
is an FP NP computable function. The sample points z z d that
are returned in this case have the following properties. If x 2 L then
no matter which string is returned as z i . That is for every
possible sample point z i there is a y i such that ML (x; y
for any set of sample points z that the sampler may return,
there exists a such that ML (x; y
than half of the sample points with
probability 1
. That is
Pr
"d
d
is less than 2 km . So if we let M(x; r) be the deterministic polynomial
time machine that uses r to generate d sample points and
then interprets y as <y and counts the number of accepts
of ML (x; y accepts if this number is greater than 1d we get
exactly the desired result. 2
In the next lemma we show that a string of high enough CD poly (CND poly )
can be used to derandomize an MA (AM) protocol.
Lemma 3.10
1. Let L be a language in MA and 0 <   1. There exists a deterministic
polynomial time bounded machine M , a polynomial q,  > 0 and
integers k and c such that for almost all n and every r with
2. Let L be a language in AM and 0 <   1. There exists a deterministic
polynomial time bounded machine M a polynomial q,  > 0
and integers k and c such that for almost all n and every r with
Proof .
1. Choose  < and k > 6
. Let M be the deterministic polynomial
time bounded machine corresponding to L, k and  of Lemma 3.9,
item 1. The polynomial n c will be the time bound of the machine
witnessing L 2 MA of that same lemma. We will determine q later,
but assume for now that r is a string of length (1
that CD q (r)  jrj, and for ease of notation set
Suppose x 2 L. Then it follows that there exists a y such that for all
s of length (1 1. So in particular it holds
that M(x;
Suppose x 62 L. We have to show that for all y it is the case that
Suppose that this is not true and let y 0 be such that
A x;y 0
It follows that A x;y0 2 P by essentially a program that simulates M
and has x and y 0 hardwired. (Although A x;y0 is nite and therefore
trivially in P it is crucial here that the size of the polynomial program
is roughly Because of the amplication of the MA
protocol we have that:
Since r 2 A x;y0 it follows by Lemma 3.7 that there is a polynomial p
such
On the other hand we chose r such that:
CD q (r)  jrj
which gives a contradiction for q  p.
2. Choose  < and k > 5
. Let M be the deterministic polynomial
time bounded machine corresponding to L,  and k of Lemma 3.9,
item 2. Again, n c will be the time bound of the machine now witnessing
will be determined later. Assume for now that
r is a string of length (1 c such that CND q (r)  jrj.
Suppose x 2 L. Then it follows that for all s there exists a y such that
1. So in particular there is a y r such that M(x; y r
Suppose
L. We have to show that 8yM(x;
that this is not true. Dene A 1g. Then
A x 2 NP by a program that has x hardwired, guesses a y and simulates
. Because of the amplication of the AM protocol we have that
jjA x jj  2 (1+)(1+k)m km . Since r 2 A x it follows by Lemma 3.8 there
exists a polynomial p such that:
On the other hand, we chose r such that:
CND q (r)  jrj
which gives a contradiction whenever q  p.The following corollary shows that a string of high enough CD poly complexity
can be used to derandomize a BPP machine (See also Theorem 8.2
in [BF00]).
Corollary 3.11 Let A be a set in BPP. For any  > 0 there exists a
polynomial time Turing machine M a polynomial q such that if CD q (r)
jrj with then for all x of length n it holds that x 2 A ()
Proof of Theorem 3.1. Let A be a language in MA. Let q, M , and
be as in Lemma 3.10, item 1. The nondeterministic
reduction behaves as follows on input x of length n. First guess an s of size
check that s 2 R CD
t . Set accept if and only
if there exists a y such that M(x; 1. By Corollary 3.4 it follows that
CD q (r)  jrj=2 and the correctness of the reductions follows directly from
Lemma 3.10, item 1 with
Proof of Theorem 3.2. This follows directly from Lemma 3.10, item 2.
The NP-algorithm is analogous to the one above.
Corollary 3.12 For t 2 !(n log n)
1. BPP and NP BPP are included in NP R CD
t .
2. GI 2 NP R CND
t .
It follows that if R CND
then the Graph isomorphism problem,
GI, is in NP \ coNP.
Limitations
In the previous section we showed that the set R CD
t is hard for MA under
reductions. One might wonder whether R CD
t is also hard for MA under a
stronger reduction like the deterministic polynomial time Turing reduction.
In this section we show that this, if true, will need a nonrelativizing proof.
We will derive the following theorem.
Theorem 4.1 There is a relativized world where for every polynomial t and
t; .
The proof of this theorem is given in Lemma 4.2 which says that the
statement of Theorem 4.1 is true in any world where P
NP A =poly and Theorem 4.3 which precisely shows the existence
of such a world.
Lemma 4.2 For any oracle A and 0 <   1 it holds that if EXP NP A
NP A =poly and P
t;
A
Proof . Suppose for a contradiction that the lemma is not true. If EXP NP
NP=poly then EXP  NP=poly, so EXP  PH ([Yap83]). Furthermore, if
EXP NP  NP=poly, then certainly EXP NP  EXP=poly. It then follows
from [BH92] that EXP
If (see [BFT97] for a denition) is in P. Then
by [VV86] and so NP  BPP which implies PH  BPP by [Zac88].
Finally, the fact that unique-SAT is in P is equivalent to: For all x and
y, C poly (xjy)  CD poly (xjy) + O(1), as shown in [FK96]. We can use the
proof of [FK96] to show that unique-SAT in P also implies that R CD
for a particular universal machine. (Note that we need only contradict the
assumption for one particular type of universal machine.) This then in
its turn implies by assumption that BPP and hence EXP NP are in P NP .
This however contradicts the hierarchy theorem for relativized Turing machines
[HS65]. As all parts of this proof relativize, we get the result for any
oracle. There's one caveat here. Though R CD
t;
A clearly has a meaningful in-
terpretation, to talk about P R CD
t;
A
one must of course allow P to have access
to the oracle. It is not clear that P can ask any question if the machine can
only ask question about the random strings. Therefore, one might argue
that P R CD
t;
AA
should actually be in the statement of the lemma. This does
not aect the proof.
Our universal machine, say U S , is the following. On input p; x; y, U S
uses the Cook-Levin reduction to produce a formula f on jxj variables with
the property that x satises f if and only if p accepts x. Then U S uses
the self-reducibility of f and the assumed polynomial time algorithm for
unique-SAT to make acceptance of x unique. That is rst if the number of
variables is not equal jyj it rejects. Then, using the well-known substitute
and reduce algorithm for SAT, it veries for assignments
successively obtained from the algorithm that the algorithm for
precisely accepts rejects if this algorithm accepts
both Using this universal machine every
program accepts at most one string and therefore R CD
via an obvious
predicate. As argued above, this gives us our contradiction. 2
Now we proceed to construct the oracle.
Theorem 4.3 There exists an oracle A such that EXP NP A
Proof . The proof parallels the construction from Beigel, Buhrman and Fortnow
[BBF98], who construct an oracle such that P
NP A . We will use a similar setup.
Let M A be a nondeterministic linear time Turing machine such that the
language L A dened by
is P A complete for every A.
For every oracle A, let K A be the linear time computable complete set
for NP A . Let N K A
be a deterministic machine that runs in time 2 n and
for every A accepts a language H A that is complete for EXP NP A
. We will
construct A such that there exists a n 2 bounded advice function f such that
for for all w
(Condition
(Condition 1)
Condition 0 will guarantee that
that EXP NP  NP=poly
We use the term 0-strings for the strings of the form <0; w; 1 jwj 2
> and
1-strings for the strings of the form <1; z; w; v> with
other strings we immediately put in A.
First we give some intuition for the proof. M is a linear time Turing
machine. Therefore setting the 1-strings forces the setting of the 0 strings.
Condition 0 will be automatically fullled by just describing how we set the
1-strings because they force the 0-strings as dened by Condition 0.
Fullling Condition 1 requires a bit more care since N K A
can query
exponentially long and double exponentially many 0- and 1-strings. We consider
each 1-string <1; z; w; v> as a 0-1 valued variable y <z;w;v> whose value
determines whether <1; z; w; v> is in A. The construction of A wil force a
correspondence between the computation of N K A (x) and a low degree
polynomial over variables with values in GF (2). To encode the computation
properly we use the fact that the OR function has high degree.
We will assign a polynomial p z over GF[2] to all of the 0-strings and
1-strings z. We ensure that for all z
1. If p z is in A.
2. If p z is not in A.
First for each 1-string z = <1; z; w; v> we let p z be the single variable
polynomial y <z;w;v> .
We assign polynomials to the 0-strings recursively. Note that M A (x) can
only query 0-strings with jwj
jxj. Consider an accepting computation
path  of M(x) (assuming the oracle queries are guessed correctly). Let
;m be the queries on this path and b ;m be the query
answers with b the query was guessed in A and b
Note that m
Let P be the set of accepting computation paths of M(x). We then
dene the polynomial p z for
> as follows:
Y
(p
Remember that we are working over GF[2] so addition is parity.
Setting the variables y <z;w;v> (and thus the 1-strings) forces the values of
z for the 0-strings. We have set things up properly so the following lemma
is straightforward.
Lemma 4.4 For each 0-string
> we have
2 and Condition 0 can be satised. The polynomial p z has degree at most
Proof: Simple proof by induction on jxj. 2
The construction will be done in stages. At stage n we will code all
the strings of length n of H A into A setting some of the 1-strings and
automatically the 0-strings and thus fullling both condition 0 and 1 for
this stage.
We will need to know the degree of the multivariate multilinear polynomials
representing the OR and the AND function.
Lemma 4.5 The representation of the functions OR(u um ) and the
um ) as multivariate multilinear polynomials over GF[2] requires
degree exactly m.
Proof: Every function over GF[2] has a unique representation as a multivariate
multilinear polynomial.
Note that AND is just the product and by using De Morgan's laws we
can write OR as
Y
The construction of the oracle now treats all strings of length n in lexicographic
order. First, in a forcing phase in which the oracle is set so that
all computations of N K A remain xed for future extensions of the oracle
and next a coding phase in which rst an advice string is picked and then
the computations just forced are coded in the oracle in such a way that they
can be retrieved by an NP machine with this advice string. Great care has
of course to be taken so that the two phases don't disturb each other and
do not disturb earlier stages of the construction.
We rst describe the forcing phase. Without loss of generality, we will
assume that machine N only queries strings of the form q 2 K A . Note that
since N runs in time 2 n it may query exponentially long strings to K A .
Let x 1 be the rst string of length n. When we examine the computation
of N(x 1 ) we encounter the rst query q 1 to K A . We will try to extend the
oracle A to A 0  A such that q 1 2 K A 0
. If such an extension does not exist
we may assume that q 1 will never be in K A no matter how we extend A in
the future. We must however take care that we will not disturb previous
queries that were forced to be in K A . To this end we will build a set S
containing all the previously encountered queries that were forced to be in
K A . We will only extend A such that for all q 2 S it holds that q 2 K A 0
We will call such an extension an S-consistent extension of A.
Returning to the computation of N(x 1 ) and q 1 we ask whether there is
an S-consistent extension of A such that q 1 2 K A 0
. If such an extension
exists we will choose the S-consistent extension of A which adds a minimal
number of strings to A and put q 1 in S. Next we continue the computation of
answered yes and otherwise we continue with q 1 answered
no. The next lemma shows that a minimal extension of A will never add
more than 2 3n strings to A.
Lemma 4.6 Let S be as above and q be any query to K A and suppose we are
in stage n. If there exists an S-consistent extension of A such that q 2 K A 0
then there exists one that adds at most 2 3n strings to A.
Proof . Let MK be a machine that accepts K A when given oracle A and
consider the computation of machine M A
l be the smallest
set of strings such that adding them to A is an S-consistent extension of A
such that M A 0
K (q) accepts. Consider the leftmost
accepting path of M A 0
K (q) and let q be the queries (both 0 and
1-queries) on that path. Moreover let b i be 1 . Dene for q the
following polynomial:
Y
(p
After adding the strings l to A we have that P
by Lemma 4.4 the degree of each p q i is at most 2 2n and hence the degree
of P q is at most 2 3n . Now consider what happens when we take out any
number of the strings l of A 0 resulting in A 00 . Since this was a
minimal extension of A it follows that M A 00
K (q) rejects and that P
computes the AND on the l strings . Since by Lemma 4.5 the
degree of the unique multivariate multilinear polynomial that computes the
AND over l variables over GF[2] is l it follows that l  2 3n . 2
After we have dealt with all the queries encountered on N K A
continue this process with the other strings of length n in lexicographic
order. Note that since we only extend A S-consistently we will never disturb
any computation of N K A on lexicographic smaller strings. This follows since
the queries that are forced to be yes will remain yes and the queries that
could not be forced with an S-consistent extension will never be forced by
any S 0 -consistent extension of A, for S  S 0 . After we have nished this
process we have to code all the computations of N on the strings of length
n. It is easy to see that jjSjj  2 2n and that at this point by Lemma 4.6 at
most 2 5n strings have been added to A at this stage. Closing the forcing
phase we can now pick an advice string and proceed to the coding phase. A
standard counting argument shows that there is a string z of length n 2 such
that no strings of the form <1; z; w; v> have been added to A. This string
z will be the advice for strings of length n.
Now we have to show that we can code every string x of length n correctly
in A to fulll condition 1. We will do this in lexicographic order. Suppose
we have coded all strings x j (for j < i) correctly and that we want to code
x i . There are two cases:
In this case we put all the strings <1; z; x
in A and thus set all these variables to 0. Since this does not change the
oracle it is an S-consistent extension.
properly extend A S-consistently adding
only strings of the form <1; z; x to A. The following lemma shows that
this can always be done. A proper extension of A is one that adds one or
more strings to A.
Lemma 4.7 Let jjSjj  2 2n be as above. Suppose that N K A There
exists a proper S-consistent extension of A adding only strings of the form
Proof . Suppose that no such proper S-consistent extension of A exists.
Consider the following polynomial:
Y
q2S
Where P q is dened as in Lemma 4.6, equation 2. Initially Q
the degree of Q x i  2 5n . Since every extension of A with strings of the
w> is not S consistent it follows that Q x i computes the OR
of the variables y <z;x i ;w> . Since there are 2 n 2
many of those variables we
have by Lemma 4.5 a contradiction with the degree of Q x i . Hence there
exists a proper S-consistent extension of A adding only strings of the form
properly coded into A. 2
Stage n ends after coding all the strings of length n.
This completes the proof of Theorem 4.3 2
Theorem 4.3 together with the proof of Lemma 4.2 also gives the following
corollary.
Corollary 4.8 There exists a relativized world where where EXP NP is in
BPP and
Our oracle also extends the oracle of Ko [Ko91] to CD poly complexity as
follows.
Corollary 4.9 There exists an oracle such that R CD
t; for any t 2 !(n log(n))
and  > 0 is complete for NP under strong nondeterministic reductions and
. The oracle from Theorem 4.3 is a world where coNP  BPP and
poly poly (xjy)+O(1), hence it follows that R CD
Corollary 3.12 relativizes so by Item 1 we have that BPP  NP R CD
t; . 2
As a byproduct our oracle shows the following.
Corollary 4.10 9A Unique-SAT A 2 P A and P NP A
corollary indicates that the current proof that shows that if Unique-
pcan not be improved to yield a collapse to P NP
using relativizing techniques.
5 PSPACE and cR CS
s
In this section we further study the connection between cR CS
s and interactive
proofs. So far we have established that strings that have suciently high
CND poly complexity can be used to derandomize an IP protocol that has
two rounds in such a way that the role of both the prover and the verier
can be played by an NP oracle machine. Here we will see that this is also
true for IP itself provided that the random strings have high enough space
bounded Kolmogorov complexity. The class of quantied boolean formulas
(QBF) is dened as the closure of the set of boolean variables x i and their
negations x i under the operations ^, _ , 8x i and 9x i . A QBF in which all
the variables are quantied is called closed. Other QBFs are called open.
We need the following denitions and theorems from [Sha92].
Denition 5.1 ([Sha92]) A QBF B is called simple if in the given syntactic
representation every occurrence of each variable is separated from its
point of quantication by at most one universal quantier (and arbitrarily
many other symbols).
For technical reasons we also assume that (simple) QBFs can contain
negated variables, but no other negations. This is no loss of generality since
negations can be pushed all the way down to variables.
Denition 5.2 ([Sha92]) The arithmetization of a is an
expression obtained from B by replacing every positive occurrence
of x i by variable z i , every negated occurrence of x i by (1 z i ), every ^ by
, every _ by +, every 8x i by
z i 2f0;1g , and every 9x i by
z i 2f0;1g .
It follows that the arithmetization of a (simple) QBF in closed form has
an integer value, whereas the arithmetization of an open QBF is equivalent
to a (possibly multivariate) function.
Denition 5.3 ([Sha92]) The functional form of a simple closed QBF is
the univariate function that is obtained by removing from the arithmetization
of B either
z i 2f0;1g or
z i 2f0;1g where i is the least index of a variable for
which this is possible.
be a (simple) QBF with quantiers . For
be the boolean formula obtained from B by removing all its quantiers. We
denote by ~
B the arithmetization of B 0 . It is well-known that the language
of all true QBFs is complete for PSPACE. The restriction of true QBFs to
simple QBFs remains complete.
Theorem 5.4 ([Sha92]) The language of all closed simple true QBFs is
complete for PSPACE (under polynomial time many-one reductions).
It is straightforward that the arithmetization of a QBF takes on a positive
value if and only if the QBF is true. This fact also holds relative a not
too large prime.
Theorem 5.5 ([Sha92]) A simple closed quantied boolean formula B is
true if and only if there exists a prime number P of size polynomial in
jBj such that the value of the arithmetization of B is positive modulo P .
Moreover if B is false then the value of the arithmetization of B is 0 modulo
any such prime.
Theorem 5.6 ([Sha92]) The functional form of every simple QBF can be
represented by a univariate polynomial of degree at most 3.
Theorem 5.7 ([Sha92]) For every simple QBF there exists an interactive
protocol with prover P and polynomial time bounded verier V such that:
1. When B is true and P is honest, V always accepts the proof.
2. When B is false, V accepts the proof with negligible probability.
The proof of Theorem 5.7 essentially uses Theorem 5.6 to translate a simple
QBF to a polynomial in the following way. First, the arithmetization
of a simple QBF B in closed form is an integer value V which is positive
if and only if B is true. Then, B's functional form F (recall: this is
arithmetization of the QBF that is obtained from B by deleting the rst
quantier) is a univariate polynomial p 1 of degree at most 3 which has the
property that p 1 Substituting any value r 1 in p 1 gives a
new integer value V 1 , which is of course the same value that we get when
we substitute r 1 in F . However, F (r 1 ) can again be converted to a (low
degree) polynomial by deleting its rst
P or
Q sign and the above game
can be repeated. Thus, we obtain a sequence of polynomials. From the
rst polynomial in this sequence V can be computed. The last polynomial
p n has the property that p n (r
things are needed: First, if any other sequence of polynomials q
has the property that q 1
there has to be some i where q i (r
is an intersection point of p i and q i . Second, all calculations
can be done modulo some prime number of polynomial size (Theorem 5.5).
We summarize this in the following observation, which is actually a skeleton
of the proof of Theorem 5.7.
Observation 5.8 ([Sha92],[LFKN92]) Let B be a closed simple QBF
wherein the quantiers are Q if read from left to right in its syntactic
representation. Let A be its arithmetization, and let V be the value of
A. There exist a prime number P of size polynomial in jBj such that for
any sequence r of numbers taken from [1::P ] there is a sequence of
polynomials of degree at most 3 and size polynomial in jBj such that:
1.
2.
3.
4. For any sequence of univariate polynomials q
(a)
(b) q
(c) q n (r n
there is a minimal i such that p i is an
intersection point of p i and q i .
Where all (in)equalities hold modulo P and hold modulo any prime of polynomial
size if B is false. Moreover, p i can be computed in space (jBj
from B, P , r
From this reformulation of Theorem 5.7 we obtain that for any sequence
of univariate polynomials q and sequence of values r that
items 2 and 3 in Observation 5.8 it holds that either q 1
the true value of the arithmetization of B, or there is some polynomial q i in
this sequence such that r i is an intersection point of p i and q i (where p i is as
in the Observation 5.8). As p i can be computed in quadratic space from B,
that in the latter case r i cannot have high space
bounded Kolmogorov complexity relative to B, P ,
Hence, if r i does have high space bounded Kolmogorov complexity, then r i is
not an intersection point, so the rst case must hold (i.e., the value computed
from q 1 is the true value of the arithmetization of B). The following lemma
makes this precise.
Lemma 5.9 Assume the following for B, P , n,
1. B is a simple false closed QBF on n variables.
2. P is a prime number  2 jBj of size polynomial in jBj.
3. is a sequence of polynomials of degree 3 with coecients in
4. r are numbers in [1::P ].
5.
7.
8. ~
Proof: Take all calculations modulo P . Suppose q 1 It
follows from Observation 5.8 that there exists a sequence
items 1 through 3 of that lemma. Furthermore since B is false
prime, so It
follows that there must be a minimal i such that p i 6= q i and r i is an intersection
point of p i and q i . However p i can be computed in space (jBj
from B, P and r As both p i and q i have degree at most 3, it
follows that CS n (r bounded by a constant. A contradiction. 2
This suces for the main theorem of this section. Let s be any polynomial

Theorem 5.10 PSPACE  NP cR CS s
Proof: We prove the lemma for the proof can by padding
be extended to any polynomial. There exists an NP oracle machine that
accepts the language of all simple closed true quantied boolean formulas
as follows. On input B rst check that B is simple. Guess a prime number
P of size polynomial in B, a sequence of polynomials of degree at
most 3 and with coecients in [1::P ]. Finally guess a sequence of numbers
all of size jP j. Check that:
1.
2.
3.
4. nally that
is at least jP j for all i  n.
If B is true Lemma 5.8 guarantees that these items can be guessed such
that all tests are passed. If B is false and no other test fails then Lemma 5.9
guarantees that p 1 so the rst check must fail. 2
By the fact that PSPACE is closed under complement and the fact that
cR CS
s is also in PSPACE Theorem 5.10 gives that cR CS
s is complete for
PSPACE under strong nondeterministic reductions [Lon82].
Corollary 5.11 cR CS
s is complete for PSPACE under strong nondeterministic
reductions.
Buhrman and Mayordomo [BM95] showed that for
, the set
R C
jxjg is not hard for EXP under deterministic Turing
reductions. In Theorem 5.10 we made use of the relativized Kolmogorov
complexity (i.e., CS s (xjy)). Using exactly the same proof as in [BM95] one
can prove that the set cR C
jxjg is not hard for EXP
under Turing reductions. On the other hand the proof of Theorem 5.10 also
works for this set: PSPACE  NP cR C
t . We suspect that it is possible to
extend this to show that EXP  NP cR C
t . So far, we have been unable to
prove this.

Acknowledgements

We thank Paul Vitanyi for interesting discussions and providing the title
of this paper. We also thank two anonymous referees who helped with a
number of technical issues that cleared up much o the proofs and who
pointed to us to more correct references. One of the referees also pointed
out Corollary 4.8.



--R

Trading group theory for randomness.
Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set.
NP might not be as easy as detecting unique solutions.

Resource bounded kolmogorov complexity revisited.
Resource bounded kolmogorov complexity revisited.
Six hypotheses in search of a theorem.

Superpolynomial circuits
An excursion to the kolmogorov random strings.
Complete sets and structure in subrecursive classes.
On completeness and soundness in interactive proof systems.

Generalized Kolmogorov complexity and the structure of feasible computations.
On the computational complexity of algorithms.
Two tape simulation of multitape Turing machines.
On the complexity of learning minimum time-bounded turing machines
On the complexity of random strings (extended abstract).
Personal communication.

Strong nondeterministic polynomial-time reducibilities

Completeness, the recursion theorem and e

A complexity theoretic approach to randomness.
NP is as easy as detecting unique solutions.
Some consequences of non-uniform conditions on uniform classes
Probabilistic quanti

--TR
relativization;kolmogorov complexity;interactive proofs;randomness;complexity classes;arthur-merlin;merlin-arthur