Resource-Bounded Kolmogorov Complexity Revisited.
We take a fresh look at CD complexity, where CDt(x) is the size of the smallest program that distinguishes x from all other strings in time t(|x|). We also look at CND complexity, a new nondeterministic variant of CD complexity, and time-bounded Kolmogorov complexity, denoted by C complexity.We show several results relating time-bounded C, CD, and CND complexity and their applications to a variety of questions in computational complexity theory, including the following:  Showing how to approximate the size of a set using CD complexity without using the random string as needed in Sipser's earlier proof of a similar result. Also, we give a new simpler proof of this result of Sipser's.  Improving these bounds for almost all strings, using extractors.  A proof of the Valiant--Vazirani lemma directly from Sipser's earlier CD lemma.  A relativized lower bound for CND complexity. Exact characterizations of equivalences between C, CD, and CND complexity.  Showing that satisfying assignments of a satisfiable Boolean formula can be enumerated in time polynomial in the size of the output if and only if a unique assignment can be found quickly. This answers an open question of Papadimitriou.  A new Kolmogorov complexity-based proof that BPP\subseteq\Sigma_2^p$.  New Kolmogorov complexity based constructions of the following relativized worlds: There exists an infinite set in P with no sparse infinite NP subsets.   EXP=NEXP but there exists a NEXP machine whose accepting paths cannot be found in exponential time.  Satisfying assignments cannot be found with nonadaptive queries to SAT.
Introduction
Originally designed to measure the randomness of strings, Kolmogorov complexity has become an
important tool in computability and complexity theory. A simple lower bound showing that there
exist random strings of every length has had several important applications (see [LV93, Chapter
6]).
Early in the history of computational complexity theory, many people naturally looked at resource-bounded
versions of Kolmogorov complexity. This line of research was initially fruitful and led to
some interesting results. In particular, Sipser [Sip83] invented a new variation of resource-bounded
complexity, CD complexity, where one considers the size of the smallest program that accepts the
given string and no others. Sipser used CD complexity for the first proof that BPP is contained
in the polynomial-time hierarchy.
Complexity theory has marched on for the past two decades, but resource-bounded Kolmogorov
complexity has seen little interest. Now that computational complexity theory has matured a bit,
we ought to look back at resource-bounded Kolmogorov complexity and see what new results and
applications we can draw from it.
First, we use algebraic techniques to give a new upper bound lemma for CD complexity without
the additional advice required of Sipser's Lemma [Sip83]. With this lemma, we can approximately
measure the size of a set using CD complexity.
We also give a new simpler proof of Sipser's Lemma and show how it implies the important Valiant-
lemma [VV85] that randomly isolates satisfying assignments. Surprisingly, Sipser's paper
predates the result of Valiant and Vazirani.
We define CND complexity, a variation of CD complexity where we allow nondeterministic com-
putation. We prove a lower bound for CND complexity where we show that there exists an infinite
set A such that every string in A has high CND complexity even if we allow access to A as an ora-
cle. We use this lemma to prove some negative result on nondeterministic search vs. deterministic
decision.
Once we have these tools in place, we use them to unify several important theorems in complexity
theory. We answer an open question of Papadimitriou [Pap96] characterizing exactly when the
set of satisfying assignments of a formula can be enumerated in output polynomial-time. We also
give straightforward proofs that BPP is in \Sigma p
(first proven by G'acs (see [Sip83])) and create
relativized worlds where assignments to SAT cannot be found with non adaptive queries to SAT
(first proven by Buhrman and Thierauf [BT96]), and where there exists
a NEXP machine whose accepting paths cannot be found in polynomial time (first proven by
Impagliazzo and Tardos [IT89]).
These results in their original form require a great deal of time to fully understand the proof because
either the ideas and/or technical details are quite complex. We show that by understanding
resource-bounded Kolmogorov complexity, one can see full and complete proofs of these results
without much additional effort. We also look at when polynomial-time C, CD and CND complexity
collide. We give a precise characterization of when we have equality of these classes, and
some interesting consequences thereof.
Preliminaries
We use basic concepts and notation from computational complexity theory texts like Balc'azar,
D'iaz, and Gabarr'o [BDG88] and Kolmogorov complexity from the excellent book by Li and
Vit'anyi [LV93]. We use jxj to represent the length of a string x and jjAjj to represent the number
of elements in the set A. All of the logarithms are base 2.
Formally, we define Kolmogorov complexity function C(xjy) by
where U is some fixed universal deterministic Turing machine. We define unconditional Kolmogorov
complexity by
A few basic facts about Kolmogorov complexity:
ffl The choice of U affects the Kolmogorov complexity by at most an additive constant.
ffl For some constant c, C(x) - jxj
ffl For every n and every y, there is an x such that
We will also use time-bounded Kolmogorov complexity. Fix a fully time-computable function
We define the C t (xjy) complexity function as
runs in at most t(jxj
As before we let C t different universal U may affect the complexity by at most a
constant additive factor and the time by a log t factor.
While the usual Kolmogorov complexity asks about the smallest program to produce a given string,
we may also want to know about the smallest program to distinguish a string. While this difference
affects the unbounded Kolmogorov complexity by only a constant it can make a difference for the
time-bounded case. Sipser [Sip83] defined the distinguishing complexity CD t by
(1) U(p; x; y) accepts.
rejects for all z 6= x.
runs in at most t(jzj steps for all z 2 \Sigma
Fix a universal nondeterministic Turing machine U n . We define the nondeterministic distinguishing
complexity CND t by
(1) U n (p; x; y) accepts.
rejects for all z 6= x.
runs in at most t(jzj steps for all z 2 \Sigma
Once again we let CND t
We can also allow for relativized Kolmogorov complexity. For example, CD t;A (xjy) is defined as
above except that the universal machine U has access to A as an oracle.
Since one can distinguish a string by generating it we have
Lemma 2.1 8t 9c ct
where c is a constant. Likewise, since every deterministic computation is also a nondeterministic
computation we get
Lemma 2.2 8t 9c ct
In Section 5 we examine the consequences of the converses of these lemmas.
Approximating Sets with Distinguishing Complexity
In this section we derive a lemma that enables one to deterministically approximate the density of
a set, using polynomial-time distinguishing complexity.
Lemma 3.1 1g. For all x i 2 S and at least half of the primes
Proof: For each x holds that for at most n different prime numbers p,
by the Chinese Remainder Theorem. For x i there are at most dn primes p such that
S. The prime number Theorem [Ing32] states that for any m there are
approximately m= ln(m) ? m= log(m) primes less than m. There are at least 4dn
primes less than 4dn 3 . So at least half of these primes p must have
Lemma 3.2 Let A be any set. For all strings x 2 A =n it holds that CD p;A =n
O(log n) for some polynomial p.
Proof: Fix n and let and a prime p x fulfilling the conditions of Lemma 3.1
for x.
The CD poly program for x works as follows:
input y
If y 62 A =n then REJECT
else if y mod
else REJECT
The size of the above program is jp This is 2 log(jjAjj) +O(log n). It is clear
that the program runs in polynomial time, and only accepts x. 2
We note that the above Lemma also works for CND p complexity for p some polynomial.
Corollary 3.3 Let A be a set in P. For each string x 2 A it holds
O(log(n)) for some polynomial p.
Proof: We will use the same scheme as in Lemma 3.2, now using that A 2 P and specifying
the length of x, yielding an extra log(n) term for jxj plus an additional 2 log log(n) penalty for
concatenating the strings. 2
Corollary 3.4 1. A set S is sparse if and only if for all x 2 S, CD p;S (x) - O(log(jxj)), for
some polynomial p.
2. A set S 2 P is sparse if and only if for all x 2 S, CD p (x) - O(log(jxj)), for some polynomial
p.
3. A set S 2 NP is sparse if and only if for all x 2 S, CND p (x) - O(log(jxj)), for some
polynomial p.
Proof: Lemma 3.2 yields that all strings in a sparse set have O(log(n)) CD p complexity. On
the other hand simple counting shows that for any set A there must be a string x 2 A such that
CND A (x) - log(jjAjj). 2
3.1
We can also use Lemma 3.1 to give a simple proof of the following important result due to
Sipser [Sip83].
Lemma 3.5 (Sipser) For every polynomial-time computable set A there exists a polynomial p and
constant c such that for every n, for most r in \Sigma p(n) and every x 2 A =n ,
CD p;A =n
Proof: For each k, 1 - k - n, let r k be a list of 4k(n randomly chosen numbers less than
r be the concatenation of all of the r k .
Fix x 2 A =n . Let Consider one of the numbers y
listed in r k . By the Prime Number Theorem [Ing32], the probability that y is prime and less than
2 is at least 1
. The probability that y fulfills the conditions of Lemma 3.1 for x is at
least 1
4 log
4k . With probability about 1=e n+1 ? 1=2 n+1 we have that some y in r k fulfills the
condition of Lemma 3.1.
With probability at least 1=2, for every x 2 A there is some y listed in r k fulfilling the conditions
of Lemma 3.1 for x.
We can now describe x by x mod y and the pointer to y in r. 2
Note: Sipser can get a tighter bound than c log n but for most applications the additional O(log n)
additive factor makes no substantial difference.
Comparing our Lemma 3.2 with Sipser's lemma 3.5, we are able to eliminate the random string
required by Sipser at the cost of an additional log jA =n j bits.
4 Lower Bounds
In this section we show that there exists an infinite set A such that every string in A has high
CND complexity, even relative to A.
Fortnow and Kummer [FK96] prove the following result about relativized CD complexity:
Theorem 4.1 There is an infinite set A such that for every polynomial p, CD p;A (x) - jxj=5 for
almost all x 2 A.
We extend and strengthen their result for CND complexity:
Theorem 4.2 There is an infinite set A such that CND 2
The proof of Fortnow and Kummer of Theorem 4.1 uses the fact that one can start with a large
set A of strings of the same length such that any polynomial-time algorithm on an input x in A
cannot query any other y in A. However, a nondeterministic machine may query every string of a
given length. Thus we need a more careful proof.
This proof is based on the proof of Corollary 4.3 of Goldsmith, Hemachandra and Kunen [GHK92].
In Section 7, we will also describe a rough equivalence between this result and an "X-search"
theorem of Impagliazzo and Tardos [IT89].
Proof of Theorem 4.2:
We create our sets A in stages. In stage k, we pick a large n and add to A a nonempty set of
strings B of length n such that for all nondeterministic programs p running in time 2
n such that
accepts either zero or more than one strings in A. We first create a B that makes
as many programs as possible accept zero strings in B. After that we carefully remove some strings
from B to guarantee that the rest of the programs accept at least two strings.
Let P be the set of nondeterministic programs of size less than n=4. We have We will
clock all of these programs so that they will reject if they take time more than 2
n . We also assume
that on every program p in P , input x and oracle O, p O (x) queries x.
For any set X, let
. Pick sets
that maximizes j\Deltaj + jHj such that jHj - wj\Deltaj, and for all X ' \Sigma
Note that H 6= \Sigma n since jHj - wj\Deltaj - wjP
always accepts we have that \Delta 6= P .
Our final B will be a subset of \Sigma which guarantees that for all p 2 \Delta, p AB will not accept
any strings in B. We will create B such that for all accepts at least two strings in
B. Initially let For each for each integer i, 1 do the following:
Pick a minimal X ' B such that for some y 2 X, p X (y) accepts. Fix an accepting
path and let Q p i be all the queries made on that path. Let y y,
Note that jQ p;i
n . We remove no more than jP jv2
strings in total. So if we cannot
find an appropriate X, we have violated the maximality of j\Deltaj jHj. Note that y p;i 2 X p;i ' Q p;i
and all of the X p;i are disjoint.
Initially set all of the X p;i as unmarked. For each do the following twice:
Pick an unmarked X p;i . Mark all X q;j such that X q;j " Q p;i 6= ;. Let
We have that y p;i 2 B and p B (y p;i ) accepts for every X p;i processed.
At most 2 \Delta 2
of the X q;j 's get marked before we have finished, we always can find an
unmarked X p;i .
Finally note that B ' \Sigma we have at least two y 2 B, such that p B (y)
accepts. Since also guarantees that B 6= ;. Thus we have fulfilled the requirements
for stage k. 2
Using Theorem 4.2 we get the following corollary first proved by Goldsmith, Hemachandra and
Kunen [GHK92].
Corollary 4.3 (Goldsmith-Hemachandra-Kunen) Relative to some oracle, there exists an infinite
polynomial-time computable set with no infinite sparse NP subsets.
Proof: Let A from Theorem 4.2 be both the oracle and the set in P A . Suppose A has an infinite
sparse subset S in NP A . Pick a large x such that x 2 S. Applying Corollary 3.4(3) it follows that
CND A;p (x) - O(log(n)). This contradicts the fact that x 2 S ' A and Theorem 4.2. 2
The above argument shows actually something stronger:
Corollary 4.4 Relative to some oracle, there exists an infinite polynomial-time computable set
with no infinite subset in NP of density less than 2 n=9 .
5 CD vs. C and CND
This section deals with the consequences of the assumption that one of the complexity measures C,
CD, and CND coincide for polynomial time. We will see that these assumptions are equivalent to
well studied complexity theoretic assumptions. This allows us to apply the machinery developed
in the previous sections. We will use the following function classes:
Definition 5.1 1. The class FP NP[log(n)] is the class of functions computable in polynomial
time that can adaptively access an oracle in NP at most c log(n) times, for some c.
2. The class FP NP
tt is the class of functions computable in polynomial time that can non-
adaptively access an oracle in NP.
Theorem 5.2 The following are equivalent:
1. log(jxj).
2. log(jxj).
3. FP
tt .
first need the following claim due to Lozano (see [JT95, pp. 184-185]).
5.3 FP
tt if and only if for every f in FP NP
there exists a function
2 FP, that generates a polynomial-size set such that f(x) 2 g(x).
In the following let f 2 FP NP
tt . Let y. We will see that there exists a p and c such that
log(jyj). We can assume that f(x) produces a list of queries
to SAT. Let #c be the exact number of queries in Q that are in SAT. Thus
SATjj.
Consider the following CND p program given x:
input z
use f(x) to generate Q.
guess are in SAT
guess satisfying assignments for q
REJECT if not for all q are satisfiable.
compute f(x) with q answered YES and q answered NO
ACCEPT if and only if
The size of the above program is c log(jyj), accepts only y, and runs in time p, for some polynomial p
and constant c depending only on f . It follows that also all the prefixes of y have CND p complexity
bounded by c log(jyj) O(1). By assumption there exists a polynomial p 0 and constant
d such that CD p 0
a prefix of y. Since we can enumerate and simulate all
the CD p programs of size d log(jyj) in time polynomial in jyj we can generate a list of possible
candidates for as well. It follows using Claim 5.3 that FP
tt .
y be a string such that CND p 0
be the program of length k that
this. Consider the following function:
there exists a z i of length m with the i th bit equal
to y i such that Turing machine M e , given x,
nondeterministically accepts z i in l steps
Note that if e is a CND program, that runs in l steps, then it accepts exactly one string, y of
length m. Hence f(!e; 0 l y. It is not hard to see that in general f is in FP NP
tt and by
assumption in FP NP[log(n)] via machine M . Next given i, l, and m, x and the c log(n) answers to
the NP oracle that M makes we have generated y in time p for some polynomial depending on i,
and M . Hence we have that C p (y
For the next corollary we will use some results from [JT95]. We will use the following class of
limited nondeterminism defined in [DT90].
Definition 5.4 Let f(n) be a function from IN 7! IN . The class NP[f(n)] denotes that class of
languages that are accepted by polynomial-time bounded nondeterministic machines that on inputs
of length n make at most f(n) nondeterministic moves.
Corollary 5.5 If 8p 2 9p then for any k:
1. NP[log k (n)] is included in P.
2. SAT 2 NP[ n
log k (n)
3. SAT 2 DTIME(2 n O(1= log log n)
4. There exists a polynomial q such that for every m formulae OE variables each
such that at least one is satisfiable, there exists a i such that OE i is satisfiable and
Proof: The consequences in the corollary follow from assumption FP
tt follows from Theorem 5.2. 2
We can use Corollary 5.5 to get a complete collapse if there is only a constant difference between
CD and CND complexity.
Theorem 5.6 The following are equivalent:
1.
2.
3.
Proof are easy.
combined with the the assumption we have for any formulae OE
where at least one is satisfiable that
log log(n +m)
for some satisfiable OE i . We can enumerate all the programs p of length at most c log log(n +m) and
find all the formula OE i such that p(OE
Thus given OE we can in polynomial-time create a subset of size log c (n +m) that contains
a satisfiable formula if the original list did. We then apply a standard tree-pruning algorithm to
find the satisfying assignment of any satisfiable formula. 2
A simple modification of the proof shows that Theorem 5.6 holds if we replace the constant c with
a log n for any a ! 1.
For the next corollary we will need the following definition (see [ESY84]).
Definition 5.7 A promise problem is a pair of sets (Q; R). A set L is called a solution to the
promise problem (Q; R) if 8x(x 2 Q R)). For any function f , fSAT denotes the
set of boolean formulas with at most f(n) satisfying assignments for formulae of length n.
The next theorem states that nondeterministic computations that have few accepting computations
can be "compressed" to nondeterministic computations that have few nondeterministic moves if
and only if C poly - CD poly .
Theorem 5.8 The following are equivalent:
1.
2. (1SAT,SAT) has a solution in P.
3. For all time constructible f , (fSAT,SAT) has a solution in NP[2 log(f(n)) +O(log(n))].
Proof: (1 () 2) This was proven in [FK96].
(3 and the fact [DT90] that
OE be a formula with at most f(jOEj) satisfying assignments. Lemma 3.2 yields that for every
satisfying assignment a to OE, there exists a polynomial p such that CD p (a
O(log(jOEj)). Hence (using that 1 () 2) it follows that C p 0
(a
for some constant c and polynomial p 0 . The limited nondeterministic machine now guesses a C p 0
program program e of size at most 2 log(f(jOEj)) log(jOEj), and runs it (relative to OE) and accepts
iff the generated string is a satisfying assignment to OE. 2
Corollary 5.9 FP
tt implies the following:
1. For any k the promise problem (2 log k (n) SAT,SAT) has a solution in P.
2. For any k, the class of languages that is accepted by nondeterministic machines that have at
most 2 log k (n) accepting paths on inputs of length n is included in P
Proof: This follows from Theorem 5.2, Theorem 5.8, and Corollary 5.5. 2
6 Satisfying Assignments
We show several connections between CD complexity and finding satisfying assignments of boolean
formulae. By Cook's Theorem [Coo71], finding satisfying assignments is equivalent to finding
accepting computation paths of any NP computation.
6.1 Enumerating Satisfying Assignments
Papadimitriou [Pap96] mentioned the following hypothesis:
Hypothesis 6.1 There exists a Turing machine that given a formula OE will output the set A of
satisfying assignments of OE in time polynomial in jOEj and jjAjj.
We can use CD complexity to show the following.
Theorem 6.2 Hypothesis 6.1 is equivalent to (1SAT ; SAT ) has a solution in P.
In Hypothesis 6.1, we do not require the machine to halt after printing out the assignments. If
the machine is required to halt in time polynomial in OE and jjAjj we have that Hypothesis 6.1 is
equivalent to
Proof of Theorem 6.2: The implication of (1SAT ; SAT ) having a solution in P is straightfor-
ward. We concentrate on the other direction.
3.2 and Theorem 5.8 we have that for every element x of A, C q (xjOE) -
log d+c log n for some polynomial q and constant c. We simply now try every program p in length
increasing order and enumerate p(OE) if it is a satisfying assignment of OE. 2
6.2 Computing Satisfying Assignments
In this section we turn our attention to the question of the complexity of generating a satisfying
assignment for a satisfiable formula [WT93, HNOS96, Ogi96, BKT94]. It is well known [Kre88]
that one can generate (the leftmost) satisfying assignment in FP NP . A tantalizing open question
is whether one can compute some (not necessary the leftmost) satisfying assignment in FP NP
tt .
Formalizing this question, define the function class F sat by f 2 F sat if when ' 2 SAT then f(')
is a satisfying assignment of '.
The question now becomes F sat
Translating this to a CND setting we have the
following.
Lemma 6.3 F sat
only if for all OE 2 SAT there exists a satisfying assignment
a of OE such that CND p (a j OE) - c log(jOEj) for some polynomial p and constant c.
Toda and Watanabe [WT93] showed that relative to a random oracle F sat
On the
other hand Buhrman and Thierauf [BT96] showed that there exists an oracle where F sat
;. Their result also holds relative to the set constructed in Theorem 4.2.
Theorem 6.4 Relative to the set A constructed in Theorem 4.2, F sat
Proof: For some n, let OE be the formula on n variables such that only if
tt 6= ;. It now follows by Lemma 6.3 that there exists an x 2 A such
that CND p;A (x) - O(log(jxj)) for some polynomial p, contradicting the fact that for all x 2 A,
6.3 Isolating Satisfying Assignments
In this section we take a Kolmogorov complexity view of the statement and proof of the famous
lemma [VV85]. The Valiant-Vazirani lemma gives a randomized reduction from
a satisfiable formula to another formula that with a non negligible probability has exactly one
satisfying assignment.
We state the lemma in terms of Kolmogorov complexity.
Lemma 6.5 There is some polynomial p such that for all OE in SAT and all r such that
and C(r) - jrj, there is some satisfying assignment a of OE such that CD p (ajhOE; ri) - O(log jOEj).
The usual Valiant-Vazirani lemma follows from the statement of Lemma 6.5 by choosing r and the
O(log jOEj) program randomly.
We show how to derive the Valiant-Vazirani Lemma from Sipser's Lemma (Lemma 3.5). Note
Sipser's result predates Valiant-Vazirani by a couple of years.
Proof of Lemma 6.5: Let
Consider the set A of satisfying assignments of OE. We can apply Lemma 3.5 conditioned on OE using
part of r as the random strings. Let We get that every element of A has a CD
program of length bounded by d log n for some constant c. Since two different elements from
A must have different programs, we have at least 1=n c of the strings of length d must
distinguish some assignment in A.
We use the rest of r to list n 2c different strings of length d log n. Since r is random, one of
these strings w must be a program that distinguishes some assignment a in A. We can give a CD
program for a in O(log n) bits by giving d and a pointer to w in r. 2
7 Search vs. Decision in Exponential-Time
If given a satisfiable formula, one can use binary search to find the assignment.
One might expect a similar result for exponential-time computation, i.e., if
one should find a witness of a NEXP computation in exponential time. However, the proof for
polynomial-time breaks down because as one does the binary search the input questions get too
long. Impagliazzo and Tardos [IT89] give relativized evidence that this problem is indeed hard.
Theorem 7.1 ([IT89]) There exists a relativized world where there exists a
NEXP machine whose accepting paths cannot be found in exponential time.
We can give a short proof of this theorem using Theorem 4.2.
Proof of Theorem 7.1: Let A be from Theorem 4.2.
We will encode a tally set T such that EXP be a nondeterministic
oracle machine such that M runs in time 2 n and for all B, M B is NEXP B -complete.
Initially let ;. For every string w in lexicographic order, put 1 2w into T if M A\PhiT (x) accepts.
\Phi T at the end of the construction. Since M(w) could only query strings with length at
most 2 jwj - w, this construction will give us EXP
We will show that there exists a NEXP B machine whose accepting paths cannot be found in time
exponential relative to B.
Consider the NEXP B machine M that on input n guesses a string y of length n and accepts if y
is in A. Note that M runs in time 2 jnj - n.
Suppose accepting computations of M B can be found in time 2 jnj k
relative to B. By
Theorem 4.2, we can fix some large n such that A =n 6= ; and for all x 2 A =n ,
We will show the following claim.
Assuming Claim 7.2, Theorem 7.1 follows since for each i, jw 1. We thus have our contradiction
with Equation (1).
Proof of Claim 7.2: We will construct a program p A to nondeterministically distinguish x. We
use log n bits to encode n. First p will reconstruct T using the w i 's.
Suppose we have reconstructed T up to length 2 i . By our construction of T , strings of T of length
at most 2 i+1 can only depend on oracle strings of length at most 2
of the nondeterministically verify that these are the strings in T .
Once we have T , we also have so in time 2 log k n we can find x. 2
Impagliazzo and Tardos [IT89] prove Theorem 7.1 using an "X-search" problem. We can also relate
this problem to CND complexity and Theorem 4.2.
Definition 7.3 The X-search problem has a player who given N input variables not all zero, wants
to find a one. The player can ask r rounds of l parallel queries of a certain type each and wins if
the player discovers a one.
Impagliazzo and Tardos use the following result about the X-search problem to prove Theorem 7.1.
Theorem 7.4 ([IT89]) If the queries are restricted to k-DNFs and N ? 2(klr) then the
player will lose on some non-zero setting of the variables.
One can use a proof similar to that of Theorem 7.1 to prove a similar bound for Theorem 7.4. On
needs just to apply Theorem 4.2 relative to the strategy of the player.
One can also use Theorem 7.4 to prove a variant of Theorem 4.2. Suppose Theorem 4.2 fails. For
any A and for every x in A there exists a small program that nondeterministically distinguishes x.
For some x suppose we know p. We can find x by asking a DNF question based on p about the
ith bit of x.
We do not in general know p but there are not too many possibilities. We can use an additional
round of queries to try all programs and test all the answers in parallel. This will give us a general
strategy for the X-search problem contradicting Theorem 7.4.
8 BPP in the second level of the polynomial hierarchy
One of the applications of Sipser's [Sip83] randomized version of Lemma 3.2 is the proof that BPP
is in \Sigma p
2 . We will show that the approach taken in Lemma 3.2 yields a new proof of this result. We
will first prove the following variation of Lemma 3.1.
1g. There exists a prime number p such that for all
log(n).
Proof: We consider only prime numbers between c and 2c. For x holds that for at most
log c
log(c) different prime number p x p. Moreover there are at most d   (d \Gamma 1)
different pairs of strings in S, so there exists a prime number p among the first d   (d \Gamma 1) log(n)
log(c)
prime numbers such that for all x holds that x i 6j x j mod p. Applying again the
prime number Theorem [Ing32] it follows that if we take c ? d
The idea is to use Claim 8.1 as a way to approximate the number of accepting paths of a BPP
machine M . Note that the set of accepting paths ACCEPTM(x) of M on x is in P. If this set is
"small" then there exists a prime number satisfying Claim 8.1. On the other hand if the set is "big"
no such prime number exists. This can be verified in \Sigma p
There exists a number p such that for all
pairs of accepting paths x In order to apply this idea we need the gap
between the number of accepting paths when x is in the set and when it is not to be a square: if x
is not in the set then jjACCEPT M(x) jj - k(jxj) and if x is in the set jjACCEPT M(x) jj ? k 2 (jxj).
We will apply Zuckerman's [Zuc96] oblivious sampler construction to obtain this gap.
Theorem 8.2 Let M be a probabilistic machine that witnesses that some set A is in BPP. Assume
that M(x) uses m random bits. There exists a machine M 0 that uses 3m+9m
log   (m) random bits
such that if x 2 A then Pr[M 0
Proof: Use the sampler in [Zuc96] with ffl ! 1=6,
log   (m) .2
Let A 2 BPP witnessed by probabilistic machine M . Apply Theorem 8.2 to obtain M 0 . The \Sigma palgorithm for A works as follows:
input x
Guess
log   (m)
log   (m) )
If for all
log   (m)
, and Claim 8.1 guarantees that the above
program accepts. On the other hand if x 2 A then jjACCEPT M 0
log   (m) \Gamma1 and
for every prime number
log   (m)
log   (m) ) there will be a pair of strings
in ACCEPTM 0 (x) that are not congruent modulo p. This follows because for every number p -
log   (m)
log   (m) ) at most 2 2m+18m
log   (m)
log   (m) ) different u and
it holds that u 6j v mod p. 2

Acknowledgments

We would like to thank Jos'e Balc'azar and Leen Torenvliet for their comments on this subject. We
thank John Tromp for the current presentation of the proof of Lemma 3.2. We also thank Sophie
Laplante for her important contributions to Section 5. We thank Richard Beigel, Bill Gasarch and
Leen Torenvliet for comments on earlier drafts.



--R

Structural Complexity I.
On functions computable with nonadaptive queries to NP.
The complexity of generating and checking proofs of mem- bership
The complexity of theorem-proving procedures
Classes of bounded nondeterminism.
The complexity of promise problems with applications to public-key cryptography


Computing solutions uniquely collapses the polynomial hierarchy.
The Distribution of Prime Numbers.
Decision versus search problems in super-polynomial time
Jenner and Toran.
The complexity of optimization problem.
An Introduction to Kolmogorov Complexity and Its Ap- plications
Functions computable with limited access to NP.
The complexity of knowledge representation.
A complexity theoretic approach to randomness.
NP is as easy as detecting unique solutions.
Structural analysis on the complexity of inverse functions.

--TR

--CTR
Harry Buhrman , Troy Lee , Dieter Van Melkebeek, Language compression and pseudorandom generators, Computational Complexity, v.14 n.3, p.228-255, January 2005
Troy Lee , Andrei Romashchenko, Resource bounded symmetry of information revisited, Theoretical Computer Science, v.345 n.2-3, p.386-405, 22 November 2005
Allender, NL-printable sets and nondeterministic Kolmogorov complexity, Theoretical Computer Science, v.355 n.2, p.127-138, 11 April 2006
kolmogorov complexity;CD complexity;computational complexity