Natural Proofs

1 Introduction

It is natural to ask what makes lower bound questions such as P = ? PSPACE , P = ? NP , and P = ? NC so dicult to solve. A non-technical reason for thinking they are dicult might be that some very bright people have tried and failed { but this is hardly satisfactory. A technical reason along the same lines would be provided by a reduction to these questions from another problem known to be really hard such as the Riemann Hypothesis. Perhaps the ultimate demonstration that P = ? NP is a hard problem would be to show it to be independent of set theory (ZFC).

Another way to answer this question is to demonstrate that known methods are inherently too weak to solve problems such as P = ? NP . This approach was taken in Baker, Gill, and Solovay [7], who used oracle separation results for many major complexity classes to argue that relativizing proof techniques could not solve these problems. Since relativizing proof techniques involving diagonalization and simulation were the only available tools at the time of their work, progress along known lines was ruled out.

Because of this, people began to study these problems from the vantage of Boolean circuit complexity, rather than machines. The new goal is to prove a stronger, non-uniform version of P 6 = NP , namely that SAT (or some other problem in NP ) does not have polynomial-size circuits. Many new proof techniques have been discovered and successfully applied to prove lower bounds in circuit complexity, as exempli ed by [11, 1, 40, 14, 27, 28, 3, 2, 37, 4, 29, 36, 8, 5, 23, 24, 15, 13, 17, 26, 6] among others, although the lower bounds have not come up near the level of P or even NC . These techniques are highly combinatorial, and in principle they are not subject to relativization. They exist in a much larger variety than their recursion-theoretic predecessors. Even so, in this paper we give evidence of a general limitation on their ability to resolve P = ? NP and other hard problems.

Section 2 introduces and formalizes the notion of a natural proof . We argue that all lower bound proofs known to date against non-monotone Boolean circuits are natural, or can be represented as natural . In Section 3 we present diverse examples of circuit lower bound proofs and show why they are natural in our sense. While Section 5 gives some general theoretical reasons why proofs against circuits tend to be natural. Section 4 gives evidence that \naturalizable" proof techniques cannot prove strong lower bounds on circuit size . In particular, we show modulo a widely believed cryptographic assumption that no natural proof can prove super-polynomial lower bounds for general circuits , and show unconditionally that no natural proof can prove exponential lower bounds on the circuit size of the discrete logarithm problem .

Natural proofs form a hierarchy according to the complexity of the combinatorial property involved in the proof. We show without using any cryptographic assumption that AC 0 -natural proofs, which are sucient to prove the parity lower bounds of [11, 40, 14], are inherently incapable of proving the bounds for AC 0 [ q ]-circuits of [29, 36, 8].

One application of natural proofs was given in [33]. It was shown there that in certain fragments of Bounded Arithmetic any proof of super-polynomial lower bounds for general circuits would naturalize, i.e., could be recast as a natural proof. Combined with the material contained in Section 4 of this paper, this leads to the independence of such lower bounds from these theories (assuming our cryptographic hardness assumption). See also [19, 34] for interpretations of this approach in terms of the propositional calculus, [10, 25] for further results in this direction, and [35] for an informal survey.

1.1. Notation and de nitions

We denote by F n the set of all Boolean functions in n variables. Most of the time, it will be convenient to think of f 2 F as a binary string of length 2 n , called the truth-table of n n f n . f n is a randomly chosen function from F n , and in general we reserve the bold face in our formulae for random objects.

The notation AC k , NC k is used in the standard sense to denote non-uniform classes. AC 0 [ m ], TC 0 and P=poly are the classes of functions computable by polynomial-size bounded-depth circuits allowing MOD - m gates, bounded-depth circuits allowing threshold gates and unbounded-depth circuits over a complete basis, respectively.

2 Natural proofs

2.1. Natural combinatorial properties

We start by de ning what we mean by a \natural combinatorial property"; natural proofs will be those that use a natural combinatorial property.

Formally, by a combinatorial property of Boolean functions we will mean a set of Boolean functions f C n F n j n 2 ! g . Thus, a Boolean function f n will possess property C n if and only if f n 2 C n . (Alternatively, we will sometimes nd it convenient to use function notation: C n ( f n ) = 1 if f n 2 C n , and C n ( f n ) = 0 if f n 62 C n .) The combinatorial property C n is natural if it contains a subset C n with the following two conditions:

Constructivity: The predicate f n 2 C n is in P . Thus, C n is computable in time which

? is polynomial in the truth table of f n ;

Largeness: j C j 2 ? O ( n ) j F j .

n n A combinatorial property C n is useful against P=poly if it satis es:

Usefulness: The circuit size of any sequence of functions f 1 ; f 2 ; : : : ; f n ; : : : , where f n 2 C n , is super-polynomial, i.e., for any constant k , for suciently large n , the circuit size of f is greater than n k .

n A proof that some function does not have polynomial-sized circuits is natural against P=poly if the proof contains, more or less explicitly, the de nition of a natural combinatorial property C n which is useful against P=poly .

Note that the de nition of a natural proof, unlike that of a natural combinatorial property, is not precise. This is because while the notion of a property being explicitly de ned in a journal paper is perfectly clear to the working mathematician, it is a bit slippery to formalize. This lack of precision will not a ect the precision of our general statements about natural proofs (see Section 4) because they will appear only in the form \there exists (no) natural proof : : : ", and should be understood as equivalent to \there exists (no) natural combinatorial property C n : : : "

The de nitions of natural property and natural proof can be explained much less formally. First, a proof that some explicit function f g n g does not have polynomial-sized circuits must plainly identify some combinatorial property C n of g n that is used in the proof. That is, the proof will show that all functions f n that have this property, including g n itself, are hard to compute. In other words, C n is useful . If f g n g 2 NP , then the proof concludes P 6 = NP . Our main contention, backed by evidence in the next section, is that current proof techniques would strongly tend to make this C n large and constructive as de ned above. (Or at least these two conditions would hold for some sub-property C n of C n .)

In order to understand the de nition of large more intuitively, let N = 2 n . Largeness requires that j C n j 1 for some xed k > 0, i.e., f has a non-negligible chance of having j F n j N k n property C n .

Constructivity is a more subtle notion to understand and justify. We take as our basic benchmark of \constructive" that f 2 C be decidable in time 2 O ( n ) , i.e., polynomial n n as a function of 2 n . Now, this is exponential in the number n of variables in f , and n this makes our concept somewhat mysterious, especially since we are going to employ it for studying computations which are polynomial in n ! The best justi cation we have is empirical: the vast majority of properties of Boolean functions or n -vertex graphs (etc.) that one encounters in combinatorics are at worst exponential-time decidable, and, as a matter of fact, known lower bounds proofs operate only with such properties. It also should be noted that even with this loose notion of constructivity we manage to prove in Section 4 strong negative results on the non-existence of natural proofs.

More speci cally, consider a commonly-envisioned proof strategy for proving P 6 = NP :

Formulate some mathematical notion of \discrepancy" or \scatter" or \variation" of the values of a Boolean function, or of an associated polytope or other structure. (In our terms, this notion would be formalized as a combinatorial property C n that is true of any function with suciently high discrepancy.)

Show by an inductive argument that polynomial-sized circuits can only compute functions of \low" discrepancy. (In our terms, this would mean showing that C n is \useful", because any function with property C n can't be computed by a polynomialsized circuit.)

Then show that SAT, or some other function in NP , has \high" discrepancy. (In our terms, this means showing that SAT has property C n .)

Our main theorem in Section 4 gives evidence that no proof strategy along these lines can ever succeed . We show that any large and constructive C n that is useful against P=poly provides a statistical test that can be used to break any polynomial-time pseudo-random number generator. Speci cally, it would violate the fairly widely believed conjecture that there exist pseudo-random generators of hardness 2 n , for some > 0 (e.g., the standard n 1 = 3 generator based on the discrete logarithm function [9] is believed to be 2 -hard).

What we are saying, subject to the truth of the hard pseudo-random generator conjecture, is this: Any proof that some function f f n g does not have small circuits must either seize on some very specialized property of f n , i.e. one shared by only a negligible fraction of functions, or must de ne a very complicated property C n , one outside the bounds of most mathematical experience. In our terms, the proof must be unnatural by violating either \largeness" or \constructivity." In Section 5 we give some solid theoretical evidence for largeness, by showing that any C n based on a formal complexity measure must be large. We do not have any similar formal evidence for constructivity, but from experience it is plausible to say that we do not yet understand the mathematics of C n outside exponential time (as a function of n ) well enough to use them e ectively in a combinatorial style proof.

We make this point in Section 3, where we argue that all known lower bound proofs against non-monotone circuits are natural by our de nition.

The best example of a purportedly unnatural argument is a traditional counting argument. The combinatorial property C n would just be something asserting that f f n g is not in P=poly (e.g., C ( f ) = 1 exactly when the complexity of f is greater than n log n ). The n n n proof that C n is large does not give us the least hint as to how to prove the existence of a large constructive subset C n C n . Moreover, a consequence of Theorem 4.1 is that if our pseudo-random generator assumption is true then such C n cannot exist at all! Thus, a counting argument is presumably not a natural argument. This poses no problem for us since counting arguments (closely associated with diagonalization arguments) have yet not proved any lower bounds for explicit functions (except when counting is used for limited purposes, as in [36, 5]. These examples perfectly t our general framework { see Sections 3.2.1, 3.4.) The question of whether (unlimited) counting or diagonalization arguments are suciently powerful to resolve barrier problems in complexity theory predates the combinatorial style lower bounds of the 1980s. Our results have nothing to say { one way or the other { concerning the future promise of diagonalization and counting arguments.

Another exception to our scheme is the list of strong lower bounds proofs against monotone circuit models [2, 3, 4, 17, 26, 27, 28, 37]. Here the issue is not constructivity { the properties used in these proofs are all feasible { but that there appears to be no good formal analogue of the largeness condition. In particular, no one has formulated a workable de nition of a \random monotone function."

All the lower bound proofs surveyed in this paper explicitly state a natural property, and so are natural proofs. In some cases this property is explicit in the original paper, while in others we need to do some work to bring out a natural property C n that yields the same lower bound. We call this latter process naturalizing the original proof. This can be subtle (see e.g. Section 3.2.1 below). Given C n , one must exhibit C n and prove that it has both the constructivity and largeness conditions. The key to doing this seems to lie in carefully analyzing the lower bound proof that used C n . In the case where a researcher intends to build a lower bound proof around some property C n , evaluating C n for naturalness might be non-trivial. Nonetheless, in light of our framework, such an evaluation could be worthwhile: if it is natural, C n is not a useful property for solving P = ? NP and similar questions. Just as a researcher might rule out an approach to lower bounds because it relativizes, he/she might rule out an approach to circuit lower bounds because it \naturalizes".

2.2. Properties which are ? -natural against with density n

It is easy and useful to extend the de nition of natural proof to a more general, parameterized version. Understanding this more general de nition is important to understanding the results as presented in this paper.

Let ? and be complexity classes. Call a combinatorial property C n ?- natural with density n if it contains C n C n with the following two conditions:

Constructivity: The predicate f n 2 C n is computable in ? (recall, C n is a set of truth-tables with 2 n bits);

Largeness: j C n j n j F n j .

A combinatorial property C n is useful against if it satis es:

Usefulness: For any sequence of functions f n , where the event f n 2 C n happens in nitely often, f f n g 62 .

A lower bound proof that some explicit function is not in is called ?- natural against with density n if it states a ?-natural property C n which is useful against with density n .

The \default" settings of our parameters will be ? = P , = P=poly , and = 2 ? O ( n ) , n as in the initial de nition. Our main result implies the negative statement that, under our pseudo-randomness assumption, no proof with these parameters can show that SAT does not have polynomial-sized circuits. In fact, as we survey the known lower bound arguments they all remain natural even when the parameters are more restrictively adjusted. We are unaware of a lower bound proof for which we cannot exhibit a C n which is P -natural with density close to one. For most known arguments, ? can be restricted to NC 2 or lower. Our full negative result (strengthened by an observation of Razborov [33]) is that, under our pseudo-randomness assumption, no property with ?=quasi-polynomial-sized circuits,

= P=poly , and = 2 ? O ( n ) can exist. Thus, our negative result rules out proofs with n much more inclusive parameters than currently known circuit lower bounds.

3 Examples of naturalizing arguments

3.1. AC 0 lower bounds for parity: AC 0 -natural

One of the rst combinatorial arguments to give people hope and direction in lower bound research was [11] where it was shown that PARITY 62 AC 0 (independently this result, using somewhat di erent machinery, was discovered in [1]). Substantial technical improvements to their bounds were subsequently given by [40, 14]. All these proofs are AC 0 -natural.

The C n used by these arguments simply says that there does not exist a restriction of the variables with the appropriate number of unassigned variables which forces f n to be a constant function. The \appropriate" number of unassigned variables is di erent in [11, 40, 14] and determines the bounds obtained.

All three papers argue explicitly that C ( f ) = 1 implies that f f g 62 AC 0 , in other n n n words, that C is useful against AC 0 . C is a natural property. In fact, we can choose n n C n = C n .

A simple counting argument shows that C n is true of a random function ( C n has the largeness condition).

C is in AC 0 ! ( C has constructivity). Indeed, suppose k is the \appropriate" number n n of unassigned variables. Given the truth table for f n as input, we compute C n ( f n ) as follows. List all n 2 n ? k = 2 O ( n ) restrictions of n ? k variables. For each one there is a k circuit of depth 2 and size 2 O ( n ) which outputs a 1 i that restriction does not leave f a n constant function. Output the AND of all these circuits. The resulting circuit has depth 3 and is polynomial-sized in 2 n .

3.2. AC 0 [ q ] lower bounds: NC 2 -natural

In this subsection we look at the proofs from [29, 36, 8] of lower bounds on the size of AC 0 [ q ]-circuits, q being a power of a prime. The naturalness of these proofs is especially transparent in the framework of [29]. Namely, we have a GF [2]-linear mapping M from F n to a matrix space, and we simply take C n to be the set of all f n 2 F n for which rank( M ( f n )) is large. After reviewing the argument in Section 3.2.1 below, it will be an exercise for the reader to show that C n ( f n ) = 1 for at least 1/2 fraction of all f n 2 F n . Since computing the rank is in NC 2 , we see that the proof is NC 2 -natural. Smolensky's proof [36] is analyzed below.

We will show in Section 4 that there is no AC 0 -natural proof against AC 0 [2]. Along with the previous subsection, this gives the insight that [29, 36, 8] had to require arguments from a stronger class than those of [11, 40, 14].

3.2.1. Smolensky's proof: a non-trivial example of naturalization

The argument given in Smolensky [36] is a perfect example of a natural circuit lower bound proof, but this is not immediately obvious. We will outline a special case of his argument:

a proof that parity does not have small AC 0 [3] circuits.

First, we recall the notion of polynomial approximation of a Boolean function. Think of the Boolean value TRUE as corresponding to the eld element ? 1 and the Boolean value FALSE as corresponding to the eld element 1. Let f be a Boolean function and p be a polynomial over Z 3 where f and p have an identical set of variable names. Any assignment A to f can be viewed as an assignment to p ; in the case p ( A ) and f ( A ) evaluate to corresponding values we consider them equal on this assignment. Otherwise, we consider them to di er. The better p approximates f , the fewer assignments on which they di er. Since we will only be interested in the values polynomials take on f? 1 ; 1 g (Boolean) assignments, we will consider polynomials to be multi-linear by default (no variable gets raised to a power greater than one).

Proof outline: Smolensky's proof has two main pieces. (1) Any function computed by a \small" AC 0 [3] circuit can be \reasonably" approximated by a \low" degree polynomial over Z 3 . (2) The parity function in n variables can't be \reasonably" approximated by a \low" degree polynomial over Z 3 . The proof of (1) is not important here and is omitted. (2) is proved by contradiction. Suppose there were a \low" degree (degree d ) polynomial p which agrees with the polynomial x 1 x 2 x 3 x n (the parity function) on all but a \small" number of Boolean assignments. Let W be the set of Boolean assignments on which they di er. Let N = 2 n . Let w be the size of the set W . We will assume that n is odd and use l 1 and l 2 to denote polynomials of degree less than n= 2. Every multi-linear polynomial q can be written in the form x 1 x n l 1 + l 2 . This means that, ignoring the inputs in W , every Z -valued function on f? 1 ; 1 g n n W (and there are 3 N ? w of them) can be represented

3 in the form pl 1 + l 2 . This representation has degree ( n ? 1) = 2 + d which by a counting argument can't represent as many as 3 N ? w functions. Contradiction.

This proof might seem to be exploiting a very particular fact about how the parity function is expressed as a polynomial; it is not obvious how this same proof would apply to a large fraction of functions. Even worse, the proof refers to a seemingly non-constructive counting argument. However, the proof technique is by its nature applicable to many functions, and counting Boolean functions eventually boils down to counting dimensions of certain linear spaces which already is feasible in our sense.

There is one choice of C n clear from the proof: C n ( f n ) = 1 if f n can't be reasonably approximated by a low degree polynomial over Z 3 (for the appropriate de nitions of reasonable and low). Part (1) of Smolensky's argument proves that C is useful against AC 0 [3].

n Why is C n natural? To see it we have to make a choice of C n .

The simple choice is C n = C n . It is fairly obvious that C n satis es the largeness condition. But what about P=poly -constructivity? It is not at all clear that there is a polynomial-size circuit which can determine if a function (given by its truth-table) can be approximated by a low-degree polynomial over Z 3 . This remains an open problem.

Thus we sink deeper into the proof and try to put

C n ( f n ) = 1 if every polynomial q can be written in the form f n l 1 + l 2 ; (1) where f n is the unique multi-linear polynomial representing f n . Then we have constructivity.

In order to see this, denote by L the vector space of all polynomials of degree less than n= 2, and by T the complementary vector space of all (multi-linear) polynomials without monomials of degree less than n= 2. The whole polynomial space is then represented as the direct sum L T and also, since n is odd, we have dim( L ) = dim( T ) = N= 2. Now, C n ( f n ) = 1 i the linear mapping f n : L ?! T taking l 2 L to the projection of f n l 2 L T onto T is one-to-one (the reader can check his understanding at this point by verifying that the parity function has this property). Thus checking that C n ( f n ) = 1 amounts to checking that a matrix easily computable from f is non-singular which can be done in NC 2 .

n For so chosen C n the largeness condition also looks plausible. But we have no easy proof of it.

We turn around this diculty by trying to extend the de nition of (1) as much as we can (so that we'll have more functions satisfying it) while preserving its spirit (so that constructivity will also be preserved) and keeping the lower bound provided by it. A short examination shows that the de nition

C n ( f n ) = 1 i dim( f n L + L ) N (1 = 2 + ) (2) which for = 1 = 2 is the same as (1), is actually as good as (1) itself for arbitrary xed

> 0. Indeed, (2) implies that at least 3 N (1 = 2+ ) ? w functions on f? 1 ; 1 g n n W can be represented by a degree ( n ? 1) = 2 + d polynomial, and the same counting argument still works.

But if we de ne C n as in (2) with = 1 = 4, we also have largeness! This immediately follows from the fact that for every f n 2 F n either C n ( f n ) = 1 or C n ( x 1 x n f n ) = 1 (cf. the proof of Theorem 5.2 a) below). 1

To show this fact, note that if dim f n L + L 3 N= 4 then C n ( f n ) = 1. Otherwise we have dim ( x 1 x n f n L + L ) =L = dim ( x 1 x n L + f n L ) = f n L

1 C can be further adjusted to be a property of density close to one, as opposed to 1 = 2.

n dim ( x 1 x n L + f n L + L ) = ( f n L + L ) = dim ( T + L ) = ( f n L + L ) N= 4

(the rst equality here comes from the observation that ( f ) 2 = 1 and thus multiplying by n f n de nes an automorphism of L T ). This gives us C n ( x 1 : : : x n f n ) = 1.

So, C is an NC 2 -natural property.

n Smolensky's proof is the most dicult example of naturalization we have encountered in our analysis. On the other hand, it perfectly illustrates the general empirical idea of \adjusting" C n in both directions in order to come up with a natural C n .

3.3. Perceptron lower bounds for parity: P -natural

In [6], it is shown that a small constant-depth circuit (over f^ ; _ ; :g ) which is allowed a single majority gate can't approximate the parity function. The authors did this by rst showing tight lower bound on the degree of a perceptron required to approximate parity to within a given . Their argument is natural.

Some de nitions from [6]. A real polynomial p strongly represents a Boolean function 2 f just in case sgn( p ( x )) = f ( x ) for all input vectors x ; such a polynomial is also called a perceptron to compute f . Let p weakly represent f just in case p is not the constant zero function on f? 1 ; 1 g n , and sgn( p ( x )) = f ( x ) for all x where p ( x ) is nonzero. The weak degree , d w ( f ), is de ned as the least k for which there exists a non-zero degree k polynomial which weakly represents f .

A natural C n stated in the paper is that f n can't be well approximated by the sign of a low degree polynomial. It is explicitly shown that any f n with property C n can't be approximated by a small, constant-depth circuit with one majority gate, i.e., C n has usefulness. To see that C n is natural one must exhibit a proper subset C n .

Let C n ( f n ) = 1 if d w ( f n ) is greater than the appropriate threshold. [6] explicitly showed that C n ( f n ) = 1 implies that a polynomial must have appropriately high degree to approximate f n with its sign, i.e., C n ( f n ) = 1 implies that C n ( f n ) = 1. d w is computable in polynomial-time using linear programming. This shows that C n has constructivity. Since the linear programming seems essential it is doubtful that anything substantially more constructive than C n could be found in the above argument, e.g., an NC -natural property for example.

2 In this section we, similarly to 3.2.1, represent Boolean functions as mappings from f? 1 ; 1 g n to f? 1 ; 1 g , and fg stands for the point-wise product, which is the same as f g in the f 0 ; 1 g -notation

To argue that C n has the largeness property, we can show the following improvement of an ( n= log n ) lower bound from [6]:

Theorem 3.1. f 2 F P [ d ( f ) n= 20] > 1 ? 2 ? 2 ( n )

For a uniformly chosen n n , w n .

Proof. We use the following well-known facts:

Proposition 3.2. Let a 1 ; : : : ; a N 2 R . Then there exist a 0 ; : : : ; a 0 2 Z such that j a 0 j

1 N i exp( O ( N log N )) (1 i N ) , and for every x 2 f? 1 ; 1 g N , i X N ! X N ! sgn a x = sgn a 0 x :

i i i i i =1 i =1 Proposition 3.3. Every integer polynomial p ( x 1 ; : : : ; x n ) of degree d which is not an identically zero on f? 1 ; 1 g n , di ers from zero on at least 2 n ? d points from f? 1 ; 1 g n .

The proof of Proposition 3.2 can be found e.g. in [21]; Proposition 3.3 is folklore. Let f n 2 F n . If f n is weakly represented by a polynomial p of degree at most n= 20, we rstly apply Proposition ! 3.2 to the vector of coecients of p . The length N of this vector is P n= 20 n 2 n ( H (1 = 20)+ o (1)) , where H ( ) is the entropy function. We nd that i =0 i p can be replaced by a polynomial p 0 with integer coecients whose bit size is at most O ( N 2 log N ) 2 n (2 H (1 = 20)+ o (1)) .

f n can be uniquely retrieved from the pair ( p 0 ; f 0 ), where f 0 is the list of values of f n n n on zeros of p 0 (arranged, say, in the lexicographic order). From Proposition 3.3 we know that the bit size of f 0 is at most 2 n ? 2 19 = 20 n , thus the bit size of the pair ( p 0 ; f 0 ) is at n H n most 2 n ? 2 19 = 20 n + 2 n (2 (1 = 20)+ o (1)) . Since 2 H (1 = 20) < 19 , the proof is completed by the

20 standard counting argument.

3.4. Lower bounds on formula size: AC 0 -natural

Andreev [5] gives a promising lower bound for the formula size of an explicit function. His bound was subsequently improved in [23, 24]. Finally, Hastad [15] gave a nearly optimal lower bound (almost n 3 ) of the formula size for Andreev's function.

Andreev's function is a Boolean function A 2 n on 2 n bits: a 1 ; a 2 ; : : : ; a n ; b 1 ; b 2 ; : : : ; b n . The a 's are partitioned into log n groups of size n= log n each. Let h j be the parity of the bits in the j th group. The bits h 1 ; h 2 ; : : : ; h log n index a number i from 1 to n . The value of the function A 2 n is the bit b i .

All these proofs work by using a shrinkage factor T which was successively improved in the last three papers until T = ~ ( n 2 ). ( ~ is the \soft Omega" notation which is like but ignores multiplicative factors of (log n ) k for constant k .)

The meaning of T is that when a formula is hit by a random restriction it is almost certain to shrink by a factor of T . Thus, to prove a formula lower bound, just show that a formula must have size s after being hit by a random restriction. It follows that the original formula had size around sn 2 .

The natural property C 2 n is that there is a restriction of b 's such that any of its extensions leaving at least one unrestricted variable in each group of a 's induces a formula of size

( n= log n ). This property is useful since a random restriction leaving (log n ) 2 unrestricted variables leaves at least one such variable in each group: for some xing of b 's, a random restriction to the a 's will shrink the formula to ( n= log n ). Obviously, A 2 n has C 2 n (simply restrict b 's so that they will encode the most complex function in log n variables) which implies that it must have formula complexity at least ~ ( n 3 ).

We can choose C 2 n = C 2 n . The fact that C 2 n has largeness is easy to prove. Constructivity is also easy if we observe that there are only 2 O ( n ) formulas of size less than n= log n .

3.5. Lower bounds against depth-2 threshold circuits:

TC 0 -natural

Hajnal et al. [13] show that the MOD-2 inner-product function requires depth-2 threshold circuits of exponential size. Any Boolean function can be viewed as a Boolean matrix by dividing the inputs into two equal sets with the left half indexing the rows and the right half indexing the columns. Seen in this way the inner-product function is a Hadamard matrix. Their proof shows that any matrix with low discrepancy can't be computed by small depth-2 threshold circuits. Choose C n to be true of all functions whose matrices have low discrepancy. Their main lemma shows that any Hadamard matrix has low discrepancy. The same argument shows that any matrix which is almost Hadamard in the sense that the dot product of any two rows or any two columns is small also has the low discrepancy property. Thus, the C n suggested by their proof is to check that the function viewed as a matrix is almost Hadamard, for the appropriate de nition of almost. It is possible to de ne \almost" so as to guarantee that C n has largeness and preserves usefulness. Constructivity: For each of the 2 O ( n ) dot products, feed the binary AND's into a threshold gate; feed the outputs of the threshold gates into a large fan-in AND. This is in TC 0 .

3.6. Lower bounds against switching-and-recti er networks:

AC 0 -natural

It was shown in [30] that any switching-and-recti er network (in particular, any nondeterministic branching program) for a large variety of symmetric functions must have size

( n ( n )), where ( n ) is a function which slowly grows to in nity. A similar result was proven in [18] for -branching programs.

The proofs are based upon a purely combinatorial characterization of the network size in terms of particular instances of the MINIMUM COVER problem. Let C n be the set of those functions f n for which the size ( f n ) of the minimal solution to the corresponding instance is ( n ( n )).

The key lemma in these proofs says that if f n outputs a 1 on any input with s ( n ) ones, and outputs a 0 on any input with s ( n ) ? d ( n ) ones, then ( f n ) ( n ( n )) ( s ( n ) and d ( n ) are functions which slowly grow to in nity; s ( n ) d ( n )).

Denote this property by A n . It obviously violates the largeness condition. We circumvent this by letting C n be the set of those functions for which any restriction assigning n= 2 variables to zero can be extended to another restriction 0 by assigning to zero ( n= 2 ? log log n ) additional variables in such a way that the induced function has A log log n .

To see C n C n , recall from [30, 18] that every covering set i; ( A ) has its associated variable x i such that restricting this variable to 0 kills i; ( A ). Now, for any collection of o ( n ( n )) covering sets we simply assign n= 2 most frequently represented x i 's to 0, and this leaves us with a collection in which every variable corresponds to at most o ( ( n )) sets. Hence, for every extension 0 of this restriction, the size of the resulting collection will be o (log log n ( n )). Thus, by the above lemma, this collection (and hence the original one) does not cover all the points from the universe ( ( n ) and (log log n ) di er by at most 1).

C is in AC 0 (cf. Section 3.1).

n To see the largeness condition, note that for every we can choose n 3 = 2 extensions 0 ; : : : ; 0 3 = 2 so that the sets of variables unassigned by every two di erent 0 ; 0 from this 1 n i j list have at most one variable in common. The event \ f n restricted by 0 has A log log n " i depends only on those inputs that have either s ( n ) or s ( n ) ? d ( n ) ones, and, moreover, all these ones correspond to variables not assigned by 0 . Since d ( n ) > 1 and s ( n ) ? d ( n ) > 1, i our assumption on 0 ; : : : ; 0 3 = 2 implies that these sets of inputs are pairwise disjoint (when

1 n i ranges over f 1 ; : : : ; n 3 = 2 g ). Hence, the events \ f restricted by 0 has A " are n i log log n independent, and we can apply the standard counting argument.

4 Inherent limitations of natural proofs

In this section, we argue that natural proofs for lower bounds are almost self-defeating . The idea is that a natural proof that some function f is not in P=poly has an associated algorithm. But just as the proof must distinguish f from a pseudo-random function in P=poly (one being hard the other not), the associated algorithm must be able to tell the di erence between the two. Thus, the algorithm can be used to break a pseudo-random generator. This is self-defeating in the sense that a natural proof that hardness exists would have as an automatic by-product an algorithm to solve a \hard" problem.

For a pseudo-random generator G : f 0 ; 1 g k ?! f 0 ; 1 g 2 k de ne its hardness H ( G ) as k k the minimal S for which there exists a circuit C of size S such that j P [ C ( G ( x )) = 1] ? P [ C ( y ) = 1] j 1 k S

(cf. [9]). Here, as usual, x is taken at random from f 0 ; 1 g k , and y is taken at random from f 0 ; 1 g 2 k .

Theorem 4.1. There (1) is no lower bound proof which is P=poly -natural against P=poly ,

H G k o G f ; g k ?! f ; g 2 k unless ( k ) 2 for every pseudo-random generator k : 0 1 0 1 in P=poly .

In particular, if 2 n -hard functions exist then there is no P=poly -natural proof (against P=poly ). Proof. For the sake of contradiction, suppose that such a lower bound proof exists and C n is associated P=poly -natural combinatorial property. Let C n C n satisfy the constructivity and largeness conditions. W.l.o.g. we may assume from the very beginning that C n = C n .

We use a slightly modi ed construction from [12]. Let G : f 0 ; 1 g k ?! f 0 ; 1 g 2 k be a k polynomial time computable pseudo-random generator, and > 0 be an arbitrary constant. Set n = d k e . We use G : f 0 ; 1 g k ?! f 0 ; 1 g 2 k for constructing a pseudo-random function generator f : f 0 ; 1 g k ?! F in the same way as in [12]. Namely, let G ; G : f 0 ; 1 g k ?!

n 0 1 f 0 ; 1 g k be the rst and the last k bits of G , respectively. For a string y 2 f 0 ; 1 g n we de ne G : f 0 ; 1 g k ?! f 0 ; 1 g k by G G G G , and for x 2 f 0 ; 1 g k let f ( x )( y ) be y y y n y n ? 1 y 1 the rst bit of G y ( x ).

Note that f ( x )( y ) is computable by poly-size circuits, hence (from the de nition of a proof natural against P=poly ) the function f ( x ) 2 F n is not in C n for any xed x 2 f 0 ; 1 g k and any suciently large k . In other words, C has empty intersection with n n 2 f g k o f ( x ) x 0 ; 1 , and this disjointness implies that C n provides a statistical test for f ( x ), with ?

j P [ C ( f ) = 1] ? P [ C ( f ( x )) = 1] j 2 O ( n ) : (3) n n n Note that this test is computable by circuits of size 2 O ( n ) .

Constructing from this a statistical test for strings in our case is even simpler than in [12]. Namely, we arrange all internal nodes of the binary tree T of height n :

v 1 ;v 2 ;:::;v (2 n ? 1) in such a way that if v i is a son of v j then i < j . Let T i be the union of subtrees of T made by f v 1 ; : : : ; v i g along with all leaves. For a leaf y of T let v i ( y ) be the root of the subtree in T i containing y . Let G i;y G y n G y n ? h ( i;y )+1 , where h ( i; y ) is the distance between v i ( y ) and y . Finally, de ne the random collection f i;n by letting f i;n ( y ) be the rst bit of G x , where x are taken from f 0 ; 1 g k uniformly and independently for all roots v i;y v i ( y ) v of trees from T i .

Since f 0 ;n is f n , and f 2 n ? 1 ;n is f ( x ), we have from (3) that for some i , j P [ C ( f ) = 1] ? P [ C ( f ) = 1] j 2 ? O ( n ) :

n i;n n i +1 ;n Fix x for all roots v of subtrees in T other than v so that the bias 2 ? O ( n ) is preserved.

v i +1 i +1 Then we have a statistical test for strings distinguishing between G x v i +1 and ( x v 0 ; x v 00 ), where v 0 ; v 00 are the two sons of v . Thus H ( G ) 2 O ( n ) 2 O ( k ) . As was arbitrary, i +1 k the result follows.

The assumption that 2 n -hard functions exist is quite plausible. For example, despite many advances in computational number theory, multiplication seems to provide a basis for a family of such functions (known factoring algorithms are suciently exponential).

Based upon lower bounds for the parity function, Nisan [22] constructed a very strong generator secure against AC 0 -attack. In fact, an easy analysis of his generator in terms of its own complexity gives the following:

Theorem 4.2. For any integer d , there exists a family G n;s F n , where s is a seed of size polynomial in n such that G 2 AC 0 [2] and G looks random for 2 O ( n ) -size depth- d n;s n;s circuits, i.e., for any polynomial-size ( in 2 n ) depth d circuit family C : F ?! f 0 ; 1 g , n n j P [ C ( f ) = 1] ? P [ C ( G ) = 1] j < 2 ? ! ( n ) : (4) n n n n; s Here s is a random seed of the appropriate size.

Theorem 4.3. There is no lower bound proof which is AC 0 -natural against AC 0 [2] .

Proof. Assume, on the contrary, that such a proof exists, and that C n has the same meaning as in the proof of Theorem 4.1. Let d be the depth of a size 2 O ( n ) circuit to compute C . Let G be the generator which is pseudo-random against depth- d 2 O ( n ) n n;s sized circuits from Theorem 4.2. From the de nition of a proof natural against AC 0 [2], for suciently large n , C n ( G n;s ) = 0. Now, (4) immediately contradicts the largeness condition.

In fact, it is clear from the above proofs that whenever a complexity class contains pseudo-random function generators that are suciently secure against ?-attack, then there is no ?-natural proof against . E.g., it is easy to see that Theorems 4.1, 4.3 are still valid for the larger class of ?-natural proofs, where ? consists of languages computable by quasi-polynomial-sized circuits. This observation is of little importance for the examples of natural proofs given in this paper. However, it is useful in the context of proofs feasible in the logical sense [33], where quasi-polynomial limitations on the complexity arise more often. Formally, we de ne P=qpoly ~ as the class of non-uniform, quasi-polynomial size log n O (1) circuits, i.e., size n .

Theorem 4.4. There is no lower bound proof which is P=qpoly ~ -natural against P=poly

H ( G ) 2 k o (1) G : f 0 ; 1 g k ?! f 0 ; 1 g 2 k unless k for every pseudo-random generator k in P=poly .

4.1. Natural proofs are not applicable to the discrete logarithm problem

It is possible (though we are unaware of any such examples) that a lower bound proof for restricted models might be natural, but cannot be applied to any explicit function. In other words, the proof might simply argue that many functions are complex without providing us with any explicit examples of such functions. Given our hardness assumption, no natural proof can prove lower bounds against P=poly whether or not the proof makes explicit what the hard function is. Avi Wigderson has pointed out that if we restrict ourselves to certain explicit functions, we can prove unconditional results in the style of Theorem 4.1. A good example of such a function is the discrete logarithm. The key point is that the discrete logarithm is known to be hard on average if and only if it is hard in the worst case. In this section, we show that there is no natural proof that the discrete logarithm requires exponential-sized circuits.

Recall from [9] that for a prime p and a generator g for Z p , the predicate B p;g ( x ) on Z p is de ned to be 1 if log g x ( p ? 1) = 2 and 0 otherwise. B p;g ( x ) was shown in [9] to be a hard bit of the discrete logarithm problem. We consider B p;g ( x ) as a Boolean function in d log p e variables (extended by, say, zeros on those inputs x which do not represent an integer in the range [1 ; p ? 1]). Our principal goal in this section is to show that no P=poly -natural proof against \suciently large" Boolean circuits can be applied to B p;g ( x ).

To explain the meaning of \suciently large", we need a couple of technical de nitions. For an integer-valued function t ( n ), let SIZE ( t ( n )) be the complexity class consisting of all functions f f n g which have circuit size O ( t ( n )). Let t ? 1 ( n ) max f x j t ( x ) n g :

We say that t ( n ) is half-exponential if it is non-decreasing and t ? 1 ( n C ) o (log t ( n )) (5) for every C > 0. The meaning of this de nition is that, roughly speaking, the second iteration of t ( n ) should grow faster than the exponent. For example, t ( n ) = 2 n is halfexponential, whereas t ( n ) = 2 (log n ) C is not.

Theorem 4.5. Let t ( n ) be an arbitrary half-exponential function. Then there is no combinatorial property C n useful against S SIZE ( t ( n )) and satisfying P=poly -constructivity and largeness conditions such that n 2 ! C n contains in nitely many functions of the form B p;g ( x ) .

Proof. Assume the contrary, and let f B g be an in nite sequence contained in S C p ;g n 2 ! n such that d log p 1 e < d log p 2 e < : : : Let k d log p e . Applying the usefulness condition to the sequence f n obtained from f B p ;g g by letting f n 0 for those n which are not of the form d log p e , we will nd in f B p ;g g an in nite subsequence where all functions have the circuit size at least t ( k ). W.l.o.g. we may assume that this is the case for our original sequence.

Let G : f 0 ; 1 g 2 k ?! f 0 ; 1 g 4 k be the standard pseudo-random generator from [9] based upon f B p ;g g . It is easy to check that the proof of [9, Theorem 3] actually extends to showing that the circuit size of f B p ;g g is polynomial in H ( G ) + k . Thus, we have t ( k ) ( H ( G ) + k ) O (1) : (6)

Now we convert G into the pseudo-random function generator f : f 0 ; 1 g 2 k ?! F n as in the proof of Theorem 4.1, where n will be speci ed a little bit later. There exists a fixed constant $C > 0$ such that for almost all $\nu$, $f_\nu(x)(y)$ is computable by circuits of size $(k_\nu + n_\nu)^C$. Let $n_\nu = t^{-1}(k_\nu^{C+1}) + 1$.

(5) implies that $t(k_\nu) > k_\nu^{C+1}$ for almost all $\nu$, since otherwise we would have $k_\nu \leq t^{-1}\left(k_\nu^{C+1}\right) \leq \log t(k_\nu) \leq (C+1)\log k_\nu$. Hence $n_\nu \leq k_\nu$. Now we have that for almost all $\nu$ every function in the image of the generator $f_\nu$ has circuit size at most $(k_\nu + n_\nu)^C \leq (2k_\nu)^C \leq k_\nu^{C+1} \leq t(n_\nu)$. Applying the usefulness condition again, we find that for almost all $\nu$, the image of the generator $f_\nu$ has the empty intersection with $C_n$. Arguing as in the proof of Theorem 4.1, we get from this

Finally note that $C_n \neq \emptyset$ for almost all $n$ (from largeness) and, thus,

(again, for almost all $n$.)

The required contradiction is now obtained simply by combining the inequalities (5) (with $n := k_\nu, C := C + 1$), (6), (7), (8):

■

Corollary 4.6. There is no combinatorial property $C_n$ useful against $\bigcap_{\epsilon > 0} SIZE\left(2^{n^\epsilon}\right)$ and satisfying P/poly-constructivity and largeness conditions such that $\bigcup_{n \in \omega} C_n$ contains infinitely many functions of the form $B_{p,g}(x)$.

Proof. $\bigcap_{\epsilon > 0} SIZE\left(2^{n^\epsilon}\right) \supseteq SIZE\left(2^{2^{\sqrt{\log n}}}\right)$, and $t(n) = 2^{2^{\sqrt{\log n}}}$ is half-exponential. ■

It is easy to see that the above proof is actually valid for an arbitrary collection $\{f_{p,g}\}$ of functions poly-time nonuniformly Turing reducible to the corresponding discrete logarithm problem in place of $\{B_{p,g}\}$.

5 **One property of formal complexity measures**

A formal complexity measure (see e.g. [38, Section 8.8], [31]) is an integer-valued function $\mu$ on $F_n$ such that $\mu(f) \leq 1$ for $f \in \{-x_1, \ldots, -x_n, x_1, \ldots, x_n\}$ and $\mu(f * g) \leq \mu(f) +$

$\mu(g)$ for all $f, g \in F_n$ and $* \in \{\wedge, \vee\}$. The meaning of this definition is that for every formal complexity measure $\mu, \mu(f)$ provides a lower bound on the formula size of $f$, and actually many known lower bounds, both for monotone and non-monotone formulae, can be viewed from this perspective. See the above-cited sources for examples. Also, for any approximation model $\mathcal{M}$ (see [39, 32] for most general definitions), we have $\rho(f * g, \mathcal{M}) \leq \rho(f, \mathcal{M}) + \rho(g, \mathcal{M}) + 1$, hence $\rho(f, \mathcal{M}) + 1$ is a formal complexity measure.

In this section we show that any formal complexity measure $\mu$ which takes a large value at a single function, must take large values almost everywhere. In particular, every combinatorial property based on such a measure automatically satisfies the largeness condition in the definition of natural property.

More specifically, we have the following:

Theorem 5.1. Let $\mu$ be a formal complexity measure on $F_n$, and $\mu(f) = t$ for some $f \in F_n$. Then:

a) for at least $1/4$ fraction of all functions $g \in F_n$, $\mu(g) \geq t/4$;

b) for any $\epsilon = \epsilon(n)$ we have that for at least $(1 - \epsilon)$ fraction of $g \in F_n$,

In fact, the main argument used in the proof of this theorem is valid for arbitrary Boolean algebras, and we formulate it as a separate result since this might be of independent interest.

Theorem 5.2. Let $B$ be a finite Boolean algebra with $N$ atoms and $S \subseteq B$.

a) if $|S| > \frac{3}{4}|B|$ then every element of $B$ can be represented in the form

b) if $S$ contains all atoms and coatoms of $B$ then every element of $B$ can be represented in the form

where $s_{ij} \in S$ and $\ell \leq O \left( \log \frac{N \cdot |B|}{|S|} \right)$.

Proof of Theorem 5.1 from Theorem 5.2. Let $S=\{g\mid \mu(g)<t/4\}$ for part a), and

where $\delta$ is a sufficiently small constant, for part b). Note that in part b) we may assume that $\delta\cdot\frac{t}{(n+\log\frac{1}{\epsilon})^2}\geq n+1$ since otherwise there is nothing to prove. Since $\mu(\bigwedge_{i=1}^n p_i)\leq n$ and $\mu(\bigvee_{i=1}^n p_i)\leq n$, where $p_i$ is either $x_i$ or $\neg x_i$, this implies that $S$ contains all atoms and coatoms of $F_n$, the latter being viewed as a Boolean algebra.

Now, if $|S|\geq\frac{3}{4}|B|$ in part a) or $|S|\geq\epsilon|B|$ in part b), then we would apply Theorem 5.2 and represent $f$ in the form (9), (10) respectively. This representation in both cases would imply the bound $\mu(f)<t$, the contradiction.■

Now we prove Theorem 5.2. Denote by $b$ a randomly chosen element of $B$.

Proof of Theorem 5.2 a). Fix $b_0\in B$ and consider the representation

As all four random variables $b$, $(\neg b\oplus b_0)$, $\neg b$, $(b\oplus b_0)$ are uniformly distributed on $B$ and $|S|>\frac{3}{4}|B|$, for at least one particular choice $b$ of $\mathbf{b}$ we have $b$, $(\neg b\oplus b_0)$, $\neg b$, $(b\oplus b_0)\in S$.■

For proving part b) of Theorem 5.2 we need the following

Lemma 5.3. Let $B$ be a finite Boolean algebra with $N$ atoms and $S\subset B$. Then there exists a subset $S_0\subset S$ of cardinality $O(\log N)$ such that $\bigwedge S_0$ contains at most $O\left(\log\frac{|B|}{|S|}\right)$ atoms.

Proof of Lemma 5.3. Let us call an atom $a$ good if $\mathbf{P}[a\leq s]\leq 2/3$ and bad otherwise. Here $s$ is picked at random from $S$.

Now, the standard entropy-counting argument gives us that there are at most

bad atoms. An equally standard argument implies that if we take a random subset $S_0\subset S$ of cardinality $C\log N$, the constant $C$ being sufficiently large, then for any good atom $a$,

Hence, for at least one particular choice $S_0$ of $S_0$, $\bigwedge S_0$ contains only bad atoms, and the lemma follows.■

Proof of Theorem 5.2 b). Denote $\frac{|S|}{|B|}$ by $\epsilon$. Once again, fix $b_0\in B$. Let us call $c\leq b_0$ good if

and bad otherwise. Note that $b\wedge b_0$ is uniformly distributed on the Boolean algebra B 0 f c j c b 0 g . Hence

P [ c is good] 2 ; (11) where c is chosen from B 0 at random.

Now, x a good c 2 B 0 . The set B ( c ) f b 2 B j b ^ b 0 = c g is a Boolean algebra. Applying Lemma 5.3 to this algebra and to S := S \ B ( c ), we come up with S 0 S of cardinality O (log N ) such that c ^ S and ( ^ S n c ) has at most O log 1 atoms. We

0 0 extend S 0 by including to it the V corresponding coatoms and nd that every good c 2 B 0 can be represented in the form s ; s 2 S; O log N .

j =1 j j Next we apply the dual version of Lemma 5.3 to the Boolean algebra B 0 and W S := f c 2 B 0 j c is good g . In view of (11), the same argument as above yields that b 0 = `i =1 c i , where c i are either good or atoms. The statement follows.

6 Conclusion

We do not conclude that researchers should give up on proving serious lower bounds. Quite the contrary, by classifying a large number of techniques that are unable to do the job we hope to focus research in a more fruitful direction. Pessimism will only be warranted if a long period of time passes without the discovery of a non-naturalizing lower bound proof.

As long as we use natural proofs we have to cope with a duality: any lower bound proof must implicitly argue a proportionately strong upper bound. In particular, we have shown that a natural proof against complexity class implicitly shows that does not contain strong pseudo-random function generators. In fact, the proof gives an algorithm to break any such generator. Seen this way, even a natural proof against NC 1 (or TC 0 ) becomes dicult or impossible. In [16] it is argued based on the hardness of subset sum that a pseudo-random function should exist in TC 0 NC 1 . Consider the plausible conjecture that there exists a (pseudo-random) function f 2 NC 1 (or TC 0 ) such that G ( x ) = n;s f ( s # x ) is a pseudo-random function generator. A natural proof that P 6 = NC 1 or P 6 = TC 0 would give an algorithm to break it. Thus, we see that working on lower bounds using natural methods is like breaking a secret code determined by the class we are working against!

With this duality in mind, it is no coincidence that the technical lemmas of [14, 36, 29] yield much of the machinery for the learning result of [20].

7 Acknowledgements

We would like to thank Oded Goldreich, Russell Impagliazzo, Mauricio Karchmer, Silvio Micali, Robert Solovay, and Avi Wigderson for very helpful discussions. We are also indebted to both anonymous referees of the journal version of this paper for many useful comments and remarks.