Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/~anromash/ps/tcs2005.pdf Äàòà èçìåíåíèÿ: Wed Mar 21 14:44:54 2012 Äàòà èíäåêñèðîâàíèÿ: Tue Oct 2 11:28:10 2012 Êîäèðîâêà: Ïîèñêîâûå ñëîâà: images

RESOURCE BOUNDED SYMMETRY OF INFORMATION REVISITED
Troy Lee and Andrei Romashchenko March 10, 2005
Abstract. The information contained in a string x about a string y is the difference between the Kolmogorov complexity of y and the conditional Kolmogorov complexity of y given x, i.e., I (x : y ) = C(y ) - C(y | x). The Kolmogorov­Levin Theorem says that I (x : y ) is symmetric up to a small additive term. We investigate if this property also holds for several versions of polynomial time bounded Kolmogorov complexity. We study symmetry of information for some variants of distinguishing complexity CD where CD(x) is the length of a shortest program which accepts x and only x. We show relativized worlds where symmetry of information does not hold in a strong way for deterministic and nondeterministic polynomial time distinguishing complexities CDpoly and CNDpoly . On the other hand, for nondeterministic polynomial time distinguishing complexity with randomness, CAMDpoly , we show that symmetry of information holds for most pairs of strings in any set in NP. Our techniques extend work of Buhrman et al. (CCC 2004) on language compression by AM algorithms, and have the following application to the compression of samplable sources, introduced in Trevisan et al. (CCC 2004): any element x in the support of a polynomial time samplable source X can be given a description of size - log Pr[X = x] + O(log3 n), from which x can be recovered by an AM algorithm. Keywords. Kolmogorov complexity, Symmetry of information Sub ject classification. 68Q30, 68Q15

1. Intro duction
One of the most beautiful theorems in Kolmogorov Complexity is the principle of "Symmetry of Information", independently proven by Kolmogorov and Levin (ZL70). Roughly speaking, symmetry of information states that for any two strings x and y , the information contained in x about y is equal to the information contained in y about x, up to logarithmic factors. More formally,


2

Lee & Romashchenko

letting C(x) be the length of a shortest program which prints x, and C(y | x) be the length of a shortest program which prints y when given input x, symmetry of information can be stated as C(y ) - C(y | x) C(x) - C(x | y ). Besides its inherent attractiveness, this principle has also seen applications in diverse areas of theoretical computer science, for example in (ABK+ 02; JSV97; VV02). In this paper, we investigate the principal of symmetry of information when resource bounds are placed on the program to describe y given x. While the argument of Kolmogorov-Levin (ZL70) can be used without modification to show that symmetry of information holds for programs using exponential time or polynomial space, things become trickier with polynomial time bounds. Though this question has been around for some time, indeed as early as 1967 Kolmogorov suggested time-bounded versions of symmetry of information as an interesting avenue of research (Lev04), still few definite answers are known. See section 7.1 of (LV97) for a survey and open problems. The main contributions to the problem of polynomial time symmetry of information appear in the series of works (LM93; LW95) which show, in particular, the following: If P=NP then polynomial time symmetry of information holds (LW95). If cryptographic one-way functions exist, then polynomial time symmetry of information does not hold up to a O(log n) factor (LM93; LW95). The intuition behind the second result is, if f is a polynomial time computable one-way function, and f (x) = y , then y is simple given x. On the other hand, if x is simple in polynomial time given y then this would provide a way to invert the function, by cycling through all small programs. Revisiting these works, several interesting questions arise: Can polynomial time symmetry of information hold up to a factor larger than O(log n)? The same argument sketched above shows that if symmetry of information holds up to a factor of (n) then there do not exist polynomial time computable cryptographical functions which cannot be ) inverted in time 2(n. However, as, for example, factoring n-bit integers can be done in 2O( n) time (BJP93), it is not implausible that symmetry of information could hold up to a factor of (n) = n or even (n) = n1/2+ . It is the case that 2C (x, y ) C (x) + C (y | x), could we show (2 - )C (x, y ) C (x) + C (y | x) for some ? Can symmetry of information hold for complexity measures other than polynomial time printing complexity? En route to showing that BPP


Resource Bounded Symmetry of Information Revisited

3

is in the polynomial hierarchy, Sipser (Sip83) introduced a relaxation of printing complexity called distinguishing complexity, denoted CD. For a string x, CD(x) is the length of a shortest program which accepts x and only x. The arguments of (LM93; LW95) leave open the question if symmetry of information can hold for distinguishing complexity. Now if f is a polynomial time computable one-way permutation and f (x) = y , then CDpoly (x | y ) is constant, as with a description of f , on input z we accept if and only if f (z ) = y . More recently, distinguishing complexity measures using nondeterminism, denoted CND, and nondeterminism and randomness (based on the complexity class AM), denoted CAMD, have been introduced (BFL02; BLvM04). Does symmetry of information hold for these measures? Is there an assumption weaker than P=NP which implies polynomial time symmetry of information? Addressing the first two questions, we show relativized worlds where symmetry of information fails in a strong way for CDpoly and CNDpoly (the existence of such worlds was claimed in (BF95), though without a complete proof ). On the other hand, we show that for any set A NP symmetry of information holds for most pairs of strings x, y A with respect to the measure CAMDpoly . We also unconditionally show that Cpoly (x, y ) CAMDpoly (x) + CAMDpoly (y | x). This implies that symmetry of information holds under the condition Cpoly (x | y ) CAMDpoly (x | y ). We show that this statement, however, is equivalent to P=NP. The main tool of our positve results is an extension of the language compression technique of (BLvM04). This extension itself has an interesting implication for the compression of samplable sources, the study of which is introduced in (TVZ04). We show that for any polynomial time samplable source X , any element x in the support of X can be given a description of size - log Pr[X = x] + log3 n, such that x can be recovered from this description by an AM algorithm. Note that this means the source can be compressed to expected length H (X ) + O(log3 n), differing from optimal by just a O(log3 n) additive factor. Another interesting approach to the definition of time-bounded Kolmogorov complexity is L. Levin's Kt complexity introduced in (Lev73). Recently D. Ronneburger proved that symmetry of information does not hold for Kt complexity in a very strong sense (Ron04).


4

Lee & Romashchenko

2. Preliminaries
We use the following notation: denote by B the set {0, 1}; similarly, Bn is the set of all binary strings of length n; denote by |x| the length of a binary string x; denote by A the cardinality of a finite set A; for a set A B denote by A
=n

the set {x : x A and |x| = n}.
=n

for a set of pairs of strings A B â B denote by A A : |x| + |y | = n}.

the set { x, y

We will make use of the complexity classes P, NP, UP, RP, and BPP. See (Aar) for definitions. 2.1. Kolmogorov Complexity Measures. We use notation for Kolmogorov complexity from (LV97): Definition 2.1. The Kolmogorov complexity C(y | x) is defined as min{|p| : U (p, x) = y },
p

where U is a universal recursive function. Also we define C(z ) = C(z | ), where is the empty word. The choice of U affects the Kolmogorov complexity by at most an additive constant. We consider several flavors of time bounded Kolmogorov complexity.

Definition 2.2. Time t printing complexity Ct (y | x) is defined as Ct (y | x) = min{|p| : U (p, x) = y and U (p, x) runs in at most t(|x| + |y |) steps}
p

for a universal machine U . Also Ct (z ) = Ct (z | ). The choice of universal machine U affects Ct (x | y ) by at most an additive constant and the time bound t by at most a log(t) multiplicative factor. We also make use of a randomized version of printing complexity:


Resource Bounded Symmetry of Information Revisited

5

Definition 2.3. Randomized printing complexity CBPt (x | y ) is defined as the minimal length of a program p such that (i) Pr[U (p, y , r) = x] 2/3 where the probability is taken over all t(|x| + |y |) bit strings r. (ii) U (p, y , r) runs in at most t(|x| + |y |) steps for all r.

Definition 2.4. Distinguishing complexity CDt (y | x) is defined as the minimal length of a program p such that (i) U (p, x, y ) accepts, (ii) U (p, x, z ) rejects z = y , (iii) U (p, x, z ) runs in at most t(|x| + |z |) steps. Once again, CDt (z ) = CDt (z | ). There are a few other variants of distinguishing complexity. In (BFL02) a nondeterministic variant of distinguishing complexity is defined. This definition is very similar to Definition Definition 2.4 except that the universal machine is nondeterministic. This version of complexity is denoted CNDt , where t is a time bound: Definition 2.5. Let Un be a nondeterministic universal machine. Nondeterministic distinguishing complexity CNDt (y | x) is defined as the minimal length of a program p such that (i) Un (p, x, y ) accepts, (ii) Un (p, x, z ) rejects z = y , (iii) Un (p, x, z ) runs in at most t(|x| + |z |) steps. Further, in (BLvM04) a complexity based on the class AM was defined. In this case the universal machine is nondeterministic and probabilistic. This complexity is denoted CAMDt :


6

Lee & Romashchenko

Definition 2.6. Let Un be a nondeterministic universal machine. CAMDt (y | x) is defined as the minimal length of a program p such that (i) Prr [Un (p, x, y , r) accepts] > 2/3, (ii) Prr [Un (p, x, z , r) accepts] < 1/3 for all z = y , (iii) Un (p, x, z , r) runs in at most t(|x| + |z |) steps. The probabilities above are taken over all t(|x| + |y |) (respectively, t(|x| + |z |)) bit strings r. As usual, we let CNDt (z ) = CNDt (z | ), and CAMDt (z ) = CAMDt (z | ). We also use relativized version of Kolmogorov complexities, allowing the universal machine to query an oracle set. 2.2. Symmetry of Information Prop erties. Denote by C poly a version of polynomial time-bounded Kolmogorov complexity, which can be Cpoly , CDpoly , CNDpoly , or CAMDpoly . To formulate the problem of symmetry of information more precisely, we isolate three associated properties. The first is the Easy Direction of Symmetry of Information: For any polynomial p there exists a polynomial q such that for all x, y : C q(n) (x, y ) C p(n) (x) + C p(n) (y |x) + O(log(n)), where n = |x| + |y |.

(EDSI)

It is easy to verify that (EDSI) holds for any of the above complexity measures. Next is the Hard Direction of Symmetry of Information: For any polynomial p there exists a polynomial q such that for all x, y : C q(n) (x) + C q(n) (y | x) C p(n) (x, y ) + O(log(n)), where n = |x| + |y |.

(HDSI)

Finally we also consider the property of Symmetry of Mutual Information: For any polynomial p there exists a polynomial q such that for all x, y : C q (x) + C q (y | x) C p (y ) + C p (x | y ) + O(log n) (SMI)

Notice that if both (EDSI) and (HDSI) hold for a complexity measure C , then also (SMI) holds for C . The converse is not necessarily true.


Resource Bounded Symmetry of Information Revisited

7

2.3. Language Compression Theorems. A fundamental theorem of Kolmogorov complexity, and one that is very useful in applications, is the following:

Theorem 2.7 (Language Compression Theorem). For any recursively enumerable set A, and all x A=n we have C(x) log A=n + O(log n). This is as x can be described by its index in the enumeration of A=n . This theorem is essentially used in the proof of (HDSI) in the resource unbounded case given in (ZL70). Similarly, our results about resource bounded symmetry of information (both positive and negative) crucially rely on recent resource bounded language compression theorems. In (BLvM04) the following analogue of the Language Compression Theorem is shown for CND complexity.

Theorem 2.8 (BLvM04). There is a polynomial p(n) such that for any set =n A B and for all x A=n we have CNDp,A (x) log A=n + O( (n)) where (n) = ( log A=n + log(n)) log(n). Further (BLvM04) show that with the power of Arthur-Merlin protocols a Language Compression Theorem holds which is optimal up to an additive log3 n term: Theorem 2.9 (BLvM04). There is a polynomial p(n) such that for any set =n A B and for all x A=n we have CAMDp,A (x) log A=n + O(log3 (n)). For comparison we remark that for CD complexity the situation is somewhat different. In (BFL02) it is shown that there is a polynomial p(n) such that for =n any set A and for all x A=n it holds that CDp(n),A (x) 2 log A=n + O(log n). Furthermore, (BLM00) show that there is a set A where this bound is tight up to O(log n) terms. That is, the factor of 2 in general cannot be improved.

3. On CD complexity
In this section we show a relativized world where the inequalities (SMI) and, hence, (HDSI) fail in a strong way for CDpoly complexity. The proof of the next proposition follows the idea outlined in (BF95):


8

Lee & Romashchenko

Proposition 3.1. There exists an oracle A and a polynomial p(n) satisfying the following condition. For any > 0 and large enough n there exists a pair x, y Bn â Bn such that CD CD CD
2
n

,A

=2n

(y ) > (1 - )n - O(log n), (x) = O(1), (y | x) = O(1) and even C
=2n

p(n),A=2 p(n),A=2

n

n

p(n),A=2

n

(y | x) = O(1),
,A=2
n

i.e., CDp(n),A (x) + CDp(n),A (y | x) CD2 Thus, (SMI) does not hold with the oracle A.

=2n

n

(y ) + CD2

n

,A=2

n

(x | y ).

Proof. Fix n and choose an incompressible pair xn , y a mapping fn : Bn Bn as follows: fn (xn ) = yn , fn (z ) = z for all z = xn .

n

Bn â Bn . Define

Now we define A=2n . At first define two auxiliary oracles Bn and Cn : let Bn contain the graph of the function fn (on input z , i the oracle Bn returns the i-th bit of y = fn (z )) and Cn contain a single string xn (on input z Bn the oracle Cn returns 1 if and only if z = xn ). A query to Bn consists of (n + log n) bits, and a query to Cn consists of n bits. So a query to Bn Cn can be encoded as a strings of length (n + log n + 1), which is less than 2n. Thus, we may set A=2n = Bn Cn . =2n Obviously, for some polynomial p(n) we have CDp(n),A (xn ) = O(1) (it is =2n enough to query Cn to distinguish x from other stings) and Cp(n),A (yn |xn ) = O(1) (it is enough to query from Bn the value fn (xn )). n =2n On the other hand, CD2 ,A (yn ) (1 - )n - O(log n). Really, let s be a n shortest CD2 program for y , and assume |s| (1 - )n - D log n for a large enough constant D. If this program queries at some step t 2 n the point xn from the oracle Cn or any point xn , i from the oracle Bn , then C(xn | yn ) |s| + log t + O(log n), and C(xn , yn ) |yn | + |s| + log t + O(log n) < 2n.


Resource Bounded Symmetry of Information Revisited

9

We get a contradiction, as not query any `interesting' trivial oracle Bn Cn (Bn returns 0 for any string z ).

the pair xn , yn is incompressible. Hence, s does points from the oracle. Thus, it can work with a returns the i-th bit of z for any pair z , i , and Cn This means that n,

C(yn ) |s| + O(1)

and we again get a contradiction. So, we have |s| (1 - )n - O(log n).

4. On CND complexity
In this section we prove that (HDSI) and (SMI) are not true for a relativized version of polynomial time bounded CND complexity. Our proof is based on the Language Compression Theorem for CND complexity, Theorem Theorem 2.8. Theorem 4.1. Let m = m(n), s = s(n), t = t(n) be functions such that 2s and t(n)2m(
n) (n)

+ 2m(

n)

< 2n

2n-3 .

Then there is a polynomial p(n), and sets A, X such that X A
=n

Bn , X

=n

= 2s

(n)

,

=2n

Bn â Bn ,
=2n

{y : (x, y ) A
x X

} 7/8 · 2n for any x X
=2n

=n

,

{y : (x, y ) A

} 1/8 · 2n ,

and for large enough n, for all x X =n , for at least 3/4 · 2n strings y Bn the following conditions hold: x, y A=2n , CND CND CND where (n) = n log(n). n log(n) comes from Theorem Theorem 2.8.
p,A=2
n =2n

t(n),A t(n),A

(x | y ) s(n) + O( (n)), (x) m(n) - O(1), =2n (y | x) n - O(1),

Note that the term (n) =


10

Lee & Romashchenko

Corollary 4.2. There exists an oracle A such that a CNDpoly version of (HDSI) and (SMI) do not hold. Moreover, for any (0, 1) there exists a polynomial p such that for any polynomial q for large enough n (2 - )CNDp,A and CNDp,A
=2n =2n

(x, y ) < CNDq

,A

=2n

(x) + CNDq

,A

=2n

(y | x)

(y ) + CNDp,A
=2n

=2n

(x | y )

CND

q ,A

=2n

(x) + CNDq

,A

=2n

(y | x)

for most x, y A

.

Proof. It follows from Theorem Theorem 4.1 for s(n) = n/3, m(n) = (1 - /3)n, t(n) = 2n/6 . The bound (2 - ) in the first inequality of Corollary Corollary 4.2 is tight. This can be easily seen as, CNDp and CND
poly ,A=2
n

oly ,A=2

n

(x, y ) CNDp

oly ,A=2

n

(x) - O(1)

(x, y ) CNDp

oly ,A=2

n

(y | x) - O(1).

Hence for any oracle A 2CNDp,A
=2n

(x, y ) CND

q ,A

=2n

(x) + CNDq

,A

=2n

(y | x) - O(1).

Proof. (Theorem Theorem 4.1) Fix an integer n > 0. We denote by F the characteristic function of A=2n , i.e., F ( x, y ) = 1 if x, y A=2n and F (x, y ) = 0 otherwise. We define this function in a few stages: construct a sequence of functions F0 , F1 , . . . , F2m(n) -1 , Fi : Bn â Bn {0, 1, undef }. For i < j the function Fj should be an extension of Fi , i.e., a, b if Fi (a, b) = undef then Fj (a, b) = Fi (a, b). The initial function is trivial: F0 (a, b) = undef f shall define F as an extension of F2m(n) -1 . Let us introduce some notation. We say that function Fi if Fi (a, b) = 1 a, b Fi (a, b) = 0 a, b or all a, b . In the sequel we a set B Bn â Bn respects a B, B.


Resource Bounded Symmetry of Information Revisited

11

Let s1 , . . . , s2m(n) -1 be the list of all CND-programs of length less than m(n). We suppose each program sj can access an oracle O (the oracle is not fixed in advance). Also we suppose that each sj is clocked and runs at most t(n) steps. We say that sj is a wel l defined CND program for an oracle O if sO accepts j exactly one string x. Further define Fi by induction. Let the functions F0 , . . . , Fk-1 be already defined. We must construct a function Fk which is an extension of Fk-1 . Consider the program sk . There are two possibilities: 1. for any B Bn â Bn that respects Fk-1 , the program sk is not well defined for the oracle B ; 2. there exists at least one set B Bn â Bn that respects Fk-1 , and the program sk is well defined for the oracle B . The first case is trivial: we set Fk (x, y ) = Fk-1 (x, y ) for all x, y . In the second case there exists a set B and a string x such that sB accepts x in time T (B , x), k which is at most t(n), and rejects all other strings. If there is more than one such set, we choose a set B with the minimal possible T (B , x). Denote by xk the fixed string x. Let the list of all queries of the program sB (xk ) to the oracle k (for one of the shortest path, i.e., for an accepting path of length T (B , x)) be a0 , b0 , a1 , b1 , . . . , ar , br , r < t(n). We include all these pairs in the oracle. More precisely, define Fk as follows: Fk Fk Fk Fk (a, (aj (aj (a, b) = Fk-1 (a, b) , bj ) = 1 , bj ) = 0 b) = undef if if if if Fk- aj , aj , Fk- (a, bj bj 1 (a,
1

b) b)

= B, B, =

undef , j = 0, . . . , r, j = 0, . . . , r, undef and a, b = aj , bj , j.

For any set R that respects Fk , the program sR accepts the string xk in time k T (B , x). Note that for a time bound t0 T (B , x) the CND program sR may k accept also a few other strings except xk . But for any t0 < T (B , x) the program sR does not accept in time t0 any string, because we chose xk that provides k minimum to the value T (B , x). Thus, if for a time bound t0 t(n) the program sR accepts at least one string, it must accept also xk . In other words, it cannot k distinguish any string except xk . We have described an inductive procedure, which defines the functions F0 , . . ., F2m(n) -1 . At each step i we set Fi (a, b) = Fi-1 (a, b) for at most t(n)


12

Lee & Romashchenko

values a, b . Hence the function F2m(n) -1 is equal to undef for all values in Bn â Bn except for at most t(n)2m(n) values. Besides we get the list L of strings xi which can be possibly accepted by distinguishing programs sR if a set R respects F2m(n) -1 . This set is rather small: i L < 2m(n) . Further we choose an arbitrary set X of size 2s
(n) =n

Bn \ L

. Now define the function F as follows:
m(n)

F (x, y ) = F2 F (x, y ) = 1 F (x, y ) = 0

-1

(x, y )

if F2 if F2 if F2

m(n) m(n) m(n)

-1 -1 -1

(x, y ) = undef , (x, y ) = undef and x X, (x, y ) = undef and x X.
=2n

The characteristic function F defines the oracle A finished. Note that for any x X =n {y : (x, y ) A and {y : (x, y ) A
x X
=n

and the construction is

=2n

} 7/8 · 2n , } < 1/8 · 2n .
n),A
=2n

=2n

Now fix any string x0 X . Obviously, CNDt( x0 L. Further, there are at least

(x0 ) m(n) because

2n - 2m(n) t(n) - 2n-3 > 3/4 · 2n strings y such that (x0 , y ) A (x, y ) A C
A=2
n

=2n

,
=n

=2n

for any x X

, and

(y | x0 ) n - 3.

Denote by y0 any of these strings. From the conditions above it follows that CNDt(n),A (y0 | x0 ) > n - O(1) since resource bounded complexity is not less than plain complexity; CNDp(n),A (x0 | y0 ) log {x : (x, y0 ) A O( (n)) from Theorem Theorem 2.8.
=2n =2n

=2n

} + O( (n)) s(n) +


Resource Bounded Symmetry of Information Revisited

13

5. On CAMD complexity
In this section we study symmetry of information under the CAMD complexity measure. In contrast to the case of CD and CND complexity, with the power of nondeterminism and randomness we can prove some positive results, showing that some weaker versions of (HDSI) hold for CAMD. Our proof will follow the proof in the resource unbounded case as given in (ZL70). We first review this proof to see how it can be used in our case. Let , be two strings such that || + | | = n, and suppose that C(, ) = m. We define the set Ax,m = {y : C(x, y ) m}. Notice that Ax,m 2m+1 and that given x and m the set Ax,m is recursively enumerable. Thus as A,m by the Language Compression Theorem (Theorem Theorem 2.7), C( | ) log A,m + O(log n). Let k be such that 2k A,m < 2k +1 . Then the above says that C( | ) k + O(log n). Now consider the set Bm,k = {x : Ax,m 2k }. Notice that the size of Bm,k is less than 2m-k+1 , and that Bm,k . The set Bm,k is recursively enumerable given m, k , thus by the Language Compression Theorem, C() m - k + O(log n). And so C() + C( | ) m - k + k + O(log n) C(, ) + O(log n) If we substitute polynomial time printing complexity in the above argument, then the set Ax,m is in NP. Further, by the approximate lower bound counting property of AM (Bab85) there is an AM algorithm which accepts with high probability for x Bm,k and rejects with high probability for x Bm,k-1 . We have, however, no guarantee on the algorithm's behavior for x Bm,k-1 . In the next theorem, we extend the language compression results of (BLvM04) to work for AM 'gap' sets of this type, allowing the above argument to go through. This result also implies near optimal AM compression of polynomial time samplable sources, recently studied in (TVZ04). 5.1. AM compression of AM gap sets. Lemma 5.1. Let A B . Suppose there is a polynomial time bound q (n), and predicate Q such that for all u A
=n

, Pr

r Bq

(n)

[v Q(u, v , r) = 1] 2/3

{u Bn : Prr

Bq

(n)

[v Q(u, v , r) = 1] > 1/3} 2k ,


14

Lee & Romashchenko

and for all u, v , r the predicate Q(u, v , r) can be computed in polynomial time. Then there is a polynomial time bound p(n) such that for all u A=n , we have CAMDp (u) k + O(log3 n). Before going into the proof of Lemma Lemma 5.1, we briefly recall the technique of (BLvM04). Let TR : Bn â Bd Bm be the function underlying Trevisan's extractor (Tre01), that is the composition of a good error correcting code with the Nisan-Wigderson generator (NW94). The output of TR(u, e) is the evaluation of the Nisan-Wigderson generator on seed e when using u as the ^ `hard' function supplied to the generator, where u is the image of u under an ^ error correcting code. The key property of this function, what makes it a good extractor and compressor, is that if TR(u, e) is not close to uniform over choice of e Bd on some set B Bm , then u has a short description given oracle access to B . In (BLvM04) it is shown that u can be printed in polynomial time from this description and oracle access to B . This construction works for d = O(log3 n), where this term arises from the weak design construction of (RRV02). To give the elements of a set A Bn short descriptions, we let the set B be the image of A â Bd under the function TR. That is, B = xA eBd TR(x, e). Notice that for any x A, Pre [TR(x, e) B ] = 1. On the other hand if we take m to be log A + d + 1 then the probability that a uniformly chosen y Bm is in B is less than 1/2. Thus all the elements of A have a short description relative to B . Now notice that with nondeterminism and an oracle for A, we can decide membership in B , thus all the elements of A have a short CNDA description. The elements of A can be given an even more succinct CAMDA description by using the randomness in the AM protocol to simulate part of the probabilistic argument in (NW94; Tre01). Proof. (Lemma Lemma 5.1) By amplification and the results of (FGM+ 89), we can transform the predicate Q into a predicate Q taking random strings of length a polynomial q (n) and with the property if u A
=n

then Prr [v Q (u, v , r) = 1] = 1
n-2

{u : Prr [v Q (u, v , r) = 1] 2-

} 2k

for r chosen uniformly over Bq (n) . Let L = {u : Prr [v Q (u, v , r) = 1] 2-n-2 }. For each r Bq (n) we define a set Br = {w : u Bn , v , e TR(u, e) = w Q (u, v , r) = 1}


Resource Bounded Symmetry of Information Revisited

15

In the sequel we denote by Br (w) the property w Br . Clearly if u A=n , then Pre [Br (TR(u, e))] = 1, for any r Bq (n) . Now for a randomly chosen w Bm and randomly chosen r Bq (n) , we calculate the probability that w Br . As for a 0/1 variable the probability of being 1 is equal to the expectation of the variable, we have Pr[w Br ] = Er,w [Br (w)].
r,w

By linearity of expectation, we can divide the latter into two contributions, that from elements w for which u L and seed e such that TR(u, e) = w, and those w for which this is not the case. Er,w [Br (w)] =
w=TR(u,e) uL

E [Br (w)] +
w=TR(u,e) uL

E [Br (w)]

By taking m = k + d + 2 the first term can be bounded by 1/4. The second term is bounded by 2m 2-n-2 1/4. Going back to probability notation, we have for any u A=n Pr[Br (TR(u, e))] - Pr[Br (w)] 1/2.
r,e r,w

The value of Trevisan's function TR(u, e) can be viewed as a sequence of bits u1 (e) . . . um (e), ^ ^ where ui = u(e|Si ), i.e., the result of application of the boolean function u to the ^ ^ ^ i-th set of the weak design set system (for details see (RRV02) or (BLvM04)). Thus, ui depends on Si variables. By definition of a weak design the cardi^ nalities of Si for all i are equal to each other. Denote n = 2 Si . We choose a ¯ weak design system as in the proof of AM language compression in (BLvM04, Theorem 3). For this weak design n is polynomial in n. ¯ It follows by the hybrid argument that there is an i [m] and a setting of the bits of e outside of the set Si such that (5.2) Pr [Br (u1 (x) . . . ui-1 (x)ui (x)r ] - Pr [Br (u1 (x) . . . ui-1 (x)br )] 1/2m. ^ ^ ^ ^ ^
x,r,r x,r,r ,b

When the bits of the bits inside of Si bit strings. Let F (x, b, r ) do the following:

e outside of Si are fixed, all the functions ui only depend on ^ Si , thus the variable x in the above ranges uniformly over = u1 (x) . . . ui-1 (x)br . Our algorithm to approximate ui will ^ ^ ^ on input x, choose uniformly at random b, r, r and evaluate


16

Lee & Romashchenko

Br (F (x, b, r )); if this evaluates to 1, then output b, otherwise output 1 - b. Call the output of this algorithm gb (e, r, r ). We now estimate the probability that gb (e, r, r ) agrees with ui (x).
x,r,r ,b

Pr [gb (x, r, r ) = u(x)] = Pr [gb (x, r, r ) = u(x)|b = u(x)] Pr[b = u(x)] ^ ^ ^ ^
x,r,r ,b x,b

+ Pr [gb (x, r, r ) = u(x)|b = u(x)] Pr[b = u(x)] ^ ^ ^
x,r,r ,b x,b

1 = Pr [Br (F (x, b, r )) = 1|b = u(x)] ^ 2 x,r,r ,b 1 + Pr [Br (F (x, b, r )) = 0|b = u(x)] ^ 2 x,r,r ,b 11 =+ Pr [Br (F (x, b, r )) = 1|b = u(x)] ^ 2 2 x,r,r ,b - Pr [Br (F (x, b, r )) = 1|b = u(x)] ^
x,r,r ,b

=

11 + 22
x,r,r

x,r,r

Pr [Br (F (x, u(x), r )) = 1] ^

- Pr [Br (F (x, 1 - u(x), r )) = 1] ^ 1 + Pr [Br (F (x, u(x), r )) = 1] ^ 2 x,r,r ,b - Pr [Br (F (x, b, r )) = 1] =
x,r,r ,b



1 1 + 2 2m

The last line follows from Equation ((5.2)). We fix the bit b to a value b1 which preserves this prediction advantage. Notice that gb1 (x, r, r ) cannot be computed by Arthur himself, as he needs Merlin to demonstrate witnesses for acceptance in Br . We now show how the computation of gb1 (x, r, r ) can be simulated by an Arthur-Merlin protocol. We say that (r, r ) gives an -approximation to u if Prx [gb1 (x, r, r ) = ^ u(x)] . For fixed (r, r ), we identify gb1 (x, r, r ) with the string zb1 ,r,r where ^ zb1 ,r,r has bit b1 in position x if and only if gb1 (x, r, r ) = 1. For convenience we assume without loss of generality that b1 = 1 and drop the subscript. Note that with this choice the number of ones in zr is the number of strings x for which B accepts u1 (x) · · · ui-1 (x)b1 r. With w(z ) we denote the number of ones ^ ^ in a string z . Arthur randomly selects strings r1 , . . . , rs {0, 1}q (n) and r1 , . . . , rs


Resource Bounded Symmetry of Information Revisited

17

{0, 1}m-i , and asks Merlin to provide witnesses for Bri (F (x, b1 , ri )). Included as part of our description will be the average number of acceptances over all choices of r, r : a = 2-q (n) 2i-m x,r,r gb1 (x, r, r ). To limit Merlin's freedom in ¯ choosing which acceptances to demonstrate in an adverse way, we want that the total number of acceptances of the choice of r1 , . . . , rs and r1 , . . . , rs is close to the expected s · a. This is insured by an easy Chernoff bound argument: ¯ Claim 5.3. For any = (m, n) > 0, there exists s = O(n2 / 2 ) such that ¯ ¯ with probability at least 3/4 over Arthur's choice of (r1 , r1 ), . . . , (rs , rs ) the following two things will simultaneously happen: (i) A 1/8m fraction of (r1 , r1 ), . . . , (rs , rs ) will give to u. ^
1 2

+

1 4m

approximations

(ii) The total number of acceptances by B over the strings (r1 , r1 ), . . . , (rs , rs ) will be within s of the expected. That is,
s

|
j =1

w(zj ) - sa| s. ¯

Proof. we upper and use a Item (1):
x

To lower bound the probability that both of these events happen, bound the probability that each event individually does not happen union bound. Notice that for a given (r, r ), if
i-1

Pr[Br (u1 (x) · · · u ^ ^

(x)u(x)r )] - Pr[Br (u1 (x) · · · u ^ ^ ^
x

i-1

(x)b1 r )] 1/4m

^ then (r, r ) gives a ( 1 + 41 )-approximation of u. We will say that the pair (r, r ) 2 m 1 ^ is bad if it does not yield a 2 + 41 approximation to u. By Equation ((5.2)) m and Markov's inequality,
r,r

Pr[(r, r ) bad]

1 - 1/2m < 1 - 1/4m. 1 - 1/4m

By a Chernoff bound, for some constant c1 > 0, Pr
(r1 ,r1 ),...,(rs ,rs )

[ bad (1 - 1/8m)s] exp(-c1 s/m2 ).

Item (2): By a Chernoff bound, for some constant c2 > 0,
s

Pr[|1/s
j =1

w(zj ) - a| ] 2 exp(-c2 2 s/n2 ). ¯ ¯


18

Lee & Romashchenko

By taking s = c3 n2 / 2 for a sufficiently large constant c3 , the probability ¯ of each item will be less than 1/8, and the claim follows. From this point the proof follows verbatim as in the proof of AM language compression (BLvM04, Theorem 3). One application of this lemma is for the AM compression of samplable sources. The study of the compression of samplable sources is introduced in (TVZ04). They give evidence that it is unlikely that all polynomial time samplable sources can be (near) optimally compressed by probabilistic polynomial time algorithms. We show, by contrast, that with AM algorithms, and when we only consider decompression efficiency, we can achieve nearly optimal compression. Definition 5.4. Let Xn be a probability distribution on strings of length n. We say that Xn is polynomial time samplable if there is a polynomial p(n) and algorithm S such that Pr
r {0,1}
p(n)

[S (1n , r) = x] = Pr[Xn = x]

for every x {0, 1}n , and where the running time of S (1n , r) is bounded by p(n). Theorem 5.5. Let Xn be a polynomial time sampable source. There is a polynomial p(n) such that for every x in the support of Xn , CAMD
p(n)

(x) - log Pr[Xn = x] + O(log3 n).

Proof. Consider the set Lk = {x : Pr[Xn = x] 2-k }. As the source Xn is samplable, say by an algorithm S , the set {r : S (1n , r) = x} is in P. Thus by the approximate lower bound counting property of AM (Bab85), there is an AM algorithm which accepts any x Lk with probability greater than 2/3, and rejects any element x not in Lk-1 with probability greater than 2/3. Thus the total number of strings x which will be accepted by the AM lower bound counting algorithm will be less than the number of strings which receive probability more than 2-k-1 which is less than 2k+1 . Now applying Lemma Lemma 5.1 we obtain that there exists a polynomial p such that CAMDp (x) k + O(log3 n) for all x Lk . Finally, we remark that these results relativize.


Resource Bounded Symmetry of Information Revisited

19

5.2. Application to symmetry of information. Theorem 5.6. There is a polynomial p(n) such that for any set A B â B and all x, y A=n log A
=n

CAMD

p,A=

n

(x) + CAMD

p,A=

n

(y | x) - O(log3 n).

Furthermore, if A NP then there is a polynomial q (n) such that log A
=n

CAMDq (x) + CAMDq (y | x) - O(log3 n).

Proof. Fix n and , A=n . Denote m = log A=n and Ax = {y : (x, y ) A=n }. Membership in the set Ax can be decided in polynomial time given x and the oracle A=n . As A it follows from Theorem Theorem 2.9 =n that CAMDq,A ( | ) log A + O(log3 n). Now consider the set Bk = {x : Ax 2k }. Let k be such that 2k A < 2k +1 . Then Bk . By the approximate lower bound counting property of AM (Bab85), there is a predicate Q (computable in polynomial time given the oracle A=n ) such that If x Bk then Prr [y Q(x, y , r) = 1] 2/3 If x Bk
-1

then Prr [y Q(x, y , r) = 1] 1/3

Thus if Prr [y Q(x, y , r) = 1] > 1/3 then x Bk-1 . However A=n = 2m implies that Bk-1 2m-k+1 . Now by Theorem Theorem 2.9 we obtain =n CAMDq,A () m - k + O(log3 n). Putting the above together we have CAMD
q ,A
=n

() + CAMD

q ,A

=n

( |) m - k + k + O(log3 n) m + O(log3 n)

which gives the first statement of the theorem. To prove the "furthermore", note that approximate lower bound counting of NP sets can be done in AM (Bab85), and apply Lemma Lemma 5.1 to give the bound on (unrelativized) CAMD complexity of NP sets.


20

Lee & Romashchenko

Corollary 5.7. For any set A B â B and any polynomial p(n) there is a polynomial q such that for all but at most a 1/n fraction of x, y A=n , CAMD
p(n),A=
n

(x, y ) CAMD

q (n),A=

n

(x) + CAMD

q (n),A=

n

(y | x) - O(log3 n).

Furthermore, if A NP then CAMD
p(n)

(x, y ) CAMD

q (n)

(x) + CAMD

q (n)

(y | x) - O(log3 n).

Proof.

For all but at most a 1/n fraction of x, y A CAMD
p(n),A=
n

=n

we have

(x, y ) log A

=n

- O(log n).

Applying Theorem Theorem 5.6 we get the first statement of the corollary. Applying the "furthermore" of Theorem Theorem 5.6 gives the furthermore here. Theorem 5.8. For any strings x, y Bn , and polynomial p(n) there is a polynomial q (n) such that Cp (x, y ) CAMDq (x) + CAMDq (y | x) - O(log3 n). Proof. Fix a pair of strings , . Let n = || + | |, and suppose that Cp (, ) = m. Consider the set A = { x, y : C p (x, y ) m}. As membership in A can be decided in nondeterministic polynomial time, we may invoke the "furthermore" of Theorem Theorem 5.6 to give log A CAMDq () + CAMDq ( | ) - O(log3 n) for some polynomial q . On the other hand, A 2m+1 , and the theorem is proven. From Theorem Theorem 5.8 we obtain as a corollary a result of (LW95), up to an additive O(log3 (n)) factor: if P = NP then Cp (x, y ) Cq (x) + Cq (y | x) - O(log3 n). More generally, the following corollary holds. Corollary 5.9. Suppose that for any polynomial p = p(n) there is a polynomial q = q (n) such that for any x, y , Cq (x | y ) CAMDp (x | y ) + O(log3 n). Then (HDSI) holds for polynomial time printing complexity, up to an O(log3 n) additive factor.


Resource Bounded Symmetry of Information Revisited

21

6. What Implies Symmetry of Information?
Is there an assumption weaker than P=NP which would imply symmetry of information? Corollary Corollary 5.9 shows that symmetry of information (up to a log3 n factor) follows from the assumption: For any polynomial p there exists a polynomial q such that for all x, y : Cq (x | y ) CAMDp (x | y ) + O(log(n)), where n = |x| + |y |.

()

It is easily seen that this property follows from P = NP. We now see that it is in fact equivalent to P = NP. Theorem 6.1. Property () implies P = NP. We first prove the following lemma. Lemma 6.2. Suppose the following hold: NP BPP For every polynomial q there exists a polynomial p such that for all x, Cp (x) CBPq (x) + O(log |x|). Then P = NP. Proof. By the results of Ko (Ko82), the first item implies PH BPP and NP = RP. Thus to show P=NP it suffices to derandomize RP. Let L RP witnessed by a machine M running in polynimial time and using m = m(n) random bits on an input x of length n. We shall assume that m > n. By standard amplification we transform M into a polynomial machine M , which uses m(n)3 random bits and for which the probability that M (x, r) re2 3 jects when x L is less than 2-m . As the set of random strings r Bm which give the `wrong' answer is in P given x, we can apply the Language Compression Theorem for nondeterministic complexity to give that for a polynomial time bound q , CNDq (r | x) |r| - m2 + O( (m)), for any such `bad' r, where (m) = m log m as in Theorem Theorem 2.8. In particular, this means that if CNDq (r) = |r| = m3 then M (x, r) must accept. We now claim that for a given length n we can construct a string of length m = (m(n))3 with high CNDq complexity in the polynomial hierarchy. Indeed, checking that a string has maximal CND complexity can be done with a p 2


22

Lee & Romashchenko

oracle. Thus the lexicographically first string of length m with maximal CND complexity, call it r , can be found with a p oracle by doing a prefix search. 3 p This means that Cq ,3 (r ) = O(log n). As the hypothesis of the theorem implies PH BPP, and following the proof that BPPBPP = BPP, we obtain CBPq (r ) = O(log n). Finally applying the second hypothesis of the theorem we have Cp (r ) = O(log n). Thus to decide if x L we evaluate M (x, U (p)) for all programs p of length d log n for some constant d. We reject if and only if M rejects on all these computations. U will output r for one of these programs p and by the above argument, if x L then M (x, r ) must accept. Proof. (*) (Theorem Theorem 6.1) Two consequences follow from assumption

Cp (x | y ) CBPq (x | y ) + O(log n) Cp (x | y ) CNDq (x | y ) + O(log n) The second item is shown in (FK96) to imply NP = RP. This fact can be proven as follows. If if a formula with exactly one satisfying assignment a then CNDq (a | ) = O(1). Thus printing complexity being less than nondeterministic distinguishing complexity gives that unique SAT can be solved in polynomial time, and so by Valiant-Vazirani (VV86) NP = RP. We can now apply the Lemma Lemma 6.2 to obtain P = NP. A corollary of Lemma Lemma 6.2 is that polynomial time symmetry of information implies BPP = EXP. We first need the following lemma. Lemma 6.3. If (SMI) holds for polynomial time printing complexity, then for every polynomial q there is a polynomial p such that for all x, Cp (x) CBPq (x) + O(log |x|). Proof. Suppose that CBPq (x) length k such that U (p, r) = x for counting, it must be the case that r, call it r . Using (SMI), there is = k . This means there is a program p of at least 2/3 of the strings r {0, 1}q(n) . By C(r | x) |r| - O(1) for one of these strings a polynomial p for which

Cq (r ) + Cq (x | r ) Cp (x) + Cp (r | x) - O(log n). As Cq (r ) = Cp (r | x) + O(1) this implies Cp (x) k + O(log n).


Resource Bounded Symmetry of Information Revisited

23

Corollary 6.4. If for every polynomial q there exists a polynomial p such that for every x, Cp (x) CBPq (x) + O(log |x|), then BPP = EXP. In particular, if (SMI) holds for polynomial time printing complexity then BPP = EXP. Proof. Suppose, for contradiction, that EXP BPP. This implies that NP BPP, and thus by Lemma Lemma 6.2 that P = NP. We now have EXP BPP NPNP = P a contradiction to the time hierarchy theorem. We now turn to relativizations to help us find a good candidate hypothesis, weaker than P = NP, which would imply symmetry of information. As we know that symmetry of information implies the nonexistence of cryptographic oneway functions, it is natural to ask if the converse holds. This is a tantalizing hypothesis as it is known that the nonexistence of one-way functions does imply a strong compression result (Wee04, Theorem 6.3). We show that this implication does not hold in every relativized world. That is, we show there is an oracle X such that PX = UPX yet symmetry of information does not hold relative to X . Theorem 6.5. There is an oracle X such that P information does not hold relative to X .
X

= UP

X

yet symmetry of

Proof. Let X be an oracle where PX = UPX and PX = NPX . Such an oracle is constructed in (BBF98). With respect to this oracle NPX = RPX . Suppose also that symmetry of information holds relative to X . As the proofs of Lemma Lemma 6.2 and Lemma Lemma 6.3 relativize, this would then imply PX = NPX , a contradiction.

Acknowledgements
We would like to thank Leonid Levin, and Paul Vitanyi for anecdotes on the early days of symmetry of information, and Harry Buhrman and Lance Fortnow for helpful comments on (BF95) and (BFL02) and the modern history of the problem. We thank Harry Buhrman and Dieter van Melkebeek for beneficial comments and conversations about Sect. Section 5. The first author would like to thank Peter Bro Miltersen for his hospitality and many fruitful discussions during a visit in which part of this work took place. We also thank Detlef Ronneburger for sharing his result on Kt complexity and Michal Koucky for pointing out this result to us.


24

Lee & Romashchenko

References
[Aar] S. Aaronson. The complexity zoo. /~aaronson/zoo.html. http://www.cs.berkeley.edu/

[ABK+ 02] E. Allender, H. Buhrman, M. Koucky, D. van Melkebeek, and D. Ronneburger. Power from random strings. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pages 669­678. IEEE, 2002. [Bab85] L. Babai. Trading group theory for randomness. In Proceedings of the 17th ACM Symposium on the Theory of Computing, pages 421­429. ACM, 1985. [BBF98] R. Beigel, H. Buhrman, and L. Fortnow. NP might not be as easy as detecting unique solutions. In Proceedings of the 30th ACM Symposium on the Theory of Computing, pages 203­208. ACM, 1998. [BF95] H. Buhrman and L. Fortnow. Distinguishing complexity and symmetry of information. Technical Report TR-95-11, Department of Computer Science, The University of Chicago, 1995. [BFL02] H. Buhrman, L. Fortnow, and S. Laplante. Resource bounded Kolmogorov complexity revisited. SIAM Journal on Computing, 31(3):887­ 905, 2002. [BJP93] J. Buhler, H. W. Lenstra Jr., and C. Pomerance. Factoring integers with the number field sieve. In A. K. Lenstra and Jr. H. W. Lenstra, editors, The Development of the Number Field Sieve, volume 1554 of Lecture Notes in Mathematics, pages 50­94. Springer-Verlag, 1993. [BLM00] H. Buhrman, S. Laplante, and P.B. Miltersen. New bounds for the language compression problem. In Proceedings of the 15th IEEE Conference on Computational Complexity, pages 126­130. IEEE, 2000. [BLvM04] H. Buhrman, T. Lee, and D. van Melkebeek. Language compression and pseudorandom generators. In Proceedings of the 19th IEEE Conference on Computational Complexity. IEEE, 2004. [FGM+ 89] M. Furer, O. ¨ pleteness and Randomness search, pages Goldreich, Y. Mansour, M. Sipser, and S. Zachos. On comsoundness in interactive proof systems. In S. Micali, editor, and Computation, volume 5 of Advances in Computing Re429­442. JAI Press, Greenwich, 1989.


Resource Bounded Symmetry of Information Revisited

25

[FK96] L. Fortnow and M. Kummer. On resource-bounded instance complexity. Theoretical Computer Science A, 161:123­140, 1996. [JSV97] T. Jiang, J. Seiferas, and P. Vit´ yi. Two heads are better than two an tapes. Journal of the ACM, 44(2):237­256, 1997. [Ko82] K. Ko. Some observations on the probabilistic algorithms and NP-hard problems. Information Processing Letters, 14(1):39­43, 1982. [Lev73] L. A. Levin. Universal search problems. Problems Information Transmission, 9(3):265­266, 1973. [Lev04] L. A. Levin. Personal communication, 2004. [LM93] L. Longpr´ and S. Mocas. Symmetry of information and one-way funce tions. Information Processing Letters, 46(2):95­100, 1993. [LV97] M. Li and P. Vit´ yi. An Introduction to Kolmogorov Complexity and its an Applications. Springer-Verlag, New York, second edition, 1997. [LW95] L. Longpr´ and O. Watanabe. On symmetry of information and polye nomial time invertibility. Information and Compuation, 121(1):14­22, 1995. [NW94] N. Nisan and A. Wigderson. Hardness vs. randomness. Journal of Computer and System Sciences, 49:149­167, 1994. [Ron04] D. Ronneburger. Personal communication, 2004. [RRV02] R. Raz, O. Reingold, and S. Vadhan. Extracting all the randomness and reducing the error in Trevisan's extractors. Journal of Computer and System Sciences, 65(1):97­128, 2002. [Sip83] M. Sipser. A complexity theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 330­335. ACM, 1983. [Tre01] L. Trevisan. Construction of extractors using pseudo-random generators. Journal of the ACM, 48(4):860­879, 2001. [TVZ04] L. Trevisan, S. Vadhan, and D. Zuckerman. Compression of samplable sources. In Proceedings of the 19th IEEE Conference on Computational Complexity, pages 1­15. IEEE, 2004. [VV86] L. G. Valiant and V. V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85­93, 1986.


26

Lee & Romashchenko

[VV02] N. Vereshchagin and P. Vit´ yi. Kolmogorov's structure function with an an application to the foundations of model selection. In Proceedings of the 47th IEEE Symposium on Foundations of Computer Science, pages 751­760. IEEE, 2002. [Wee04] H. Wee. On pseudoentropy versus compressibility. In Proceedings of the 19th IEEE Conference on Computational Complexity. IEEE, 2004. [ZL70] A. Zvonkin and L. Levin. The complexity of finite ob jects and the algorithmic concepts of information and randomness. Russian Mathematical Surveys, 25:83­124, 1970. Troy Lee CWI and University of Amsterdam Kruislaan 413, Amsterdam 1098SJ, The Netherlands Troy.Lee@cwi.nl Andrei Romashchenko Institute for Information Transmission Problems Bolshoy Karetny 19, Moscow 101447, Russia anromash@mccme.ru