Distinguishing SAT from Polynomial-Size Circuits,

through Black-Box Queries

Albert Atserias
Universitat Politècnica de Catalunya
Barcelona, Spain
atserias@[Link]

Abstract language in
 
 from the point of view of any probabilis-
tic polynomial-time adversary. By this we mean that the
We may believe SAT does not have small Boolean cir- adversary is not able to produce, with non-negligible prob-
cuits. But is it possible that some language with small cir- ability, any instance where the languages differ on a given
cuits looks indistiguishable from SAT to every polynomial- input-length.
time bounded adversary? We rule out this possibility. More

Statement (1) consitutes a sort of worst-case to average-


precisely, assuming SAT does not have small circuits, we
show that for every language with small circuits, there
case reduction for
 

. To see why, read it in its contra-
positive form: if SAT is indistinguishable from some -


exists a probabilistic polynomial-time algorithm that makes
 

language for any efficiently samplable distribution, then it

length, a Boolean formula on which

black-box queries to , and produces, for a given input
differs from SAT.
is actually a
tion of any kind for

-language. This was the first such reduc-
. The authors in [6] stress, however,
A key step for obtaining this result is a new proof of the that the average-case hardness they obtain for SAT is not
main result by Gutfreund, Shaltiel, and Ta-Shma reducing enough for the existence of one-way functions and cryp-
average-case hardness to worst-case hardness via uniform tography. Indeed, a necessary condition for cryptography
adversaries that know the algorithm they fool. The new ad- is the existence of a single samplable distribution that is
versary we construct has the feature of being black-box on hard for all efficient algorithms simultaneously. What (1)
the algorithm it fools, so it makes sense in the non-uniform
setting as well. Our proof makes use of a refined analysis of


shows, instead, is the existence of a samplable distribution
that strongly depends on the efficient algorithm that it is
the learning algorithm of Bshouty et al.. aimed to fool. As a matter of fact, the proof shows that



the algorithm computing the distribution both simulates
and is strongly non-black-box on as it explicitely needs
1 Introduction its code. We refer the reader to the introduction of [6] for
a thorough discussion on the different versions of average-
The motivation and starting point for this article is the re- case hardness, and of worst-case to average-case reductions,
cent result of Gutfreund, Shaltiel and Ta-Shma [6] showing and their relevance to cryptography.
that if SAT is worst-case hard for probabilistic polynomial- The first contribution of this paper is a new proof of (1)
time algorithms, then, for every probabilistic polynomial-

essentially black-box on , the
 

that has the good feature of producing an adversary that is
-algorithm that sup-
time algorithm trying to solve SAT, there exists a polynomi-
ally samplable distribution that is hard for it. In the notation posedly solves SAT and that it aims to fool. What this means
invented by Kabanets:

is that the adversary gets the information it needs through

  
 implies  pseudo- 
 (1)

oracle calls to . In particular, it does not know the code
of and cannot base the production of a hard instance on

Here,
 
 denotes the class of all languages accepted by it. This partially solves a question left open in [6] where
it is asked whether reductions that are non-black-box both

ror, and the notation on the right pseudo-

 
 denotes the
probabilistic polynomial-time algorithms with bounded er- in the hard language (here SAT) and in the algorithm we
want to fool are necessary to prove (1). As pointed out be-
class of all languages that look indistinguishable from some
Supported in part by CICYT TIN2004-04343 and by the European
fore, our reduction is essentially black-box in the algorithm,
but not in the hard language as we use the downward self-
Commission through the RTN COMBSTRU HPRN-CT2002-00278. reducibility of SAT in a strong way. The technical details

1
about the exact sense in which our sampler is black-box on to use the learning algorithm of Bshouty, Cleve, Gavadà,

: 

;=<
the algorithm are discussed later in this introduction. Kannan and Tamon [3] that learns polynomial-size circuits
The main point of our new proof is, however, that the in with the help of equivalence queries. The point
technique extends easily to Boolean circuits. Thus, we show >
is that if is an algorithm that supposedly solves SAT, we


that if SAT does not have polynomial-size circuits, then for
every language with polynomial-size circuits there exists
 
may use it both to answer the equivalence queries, and to
simulate the oracle in , while trying to learn circuits for


a probabilistic polynomial-time algorithm that makes black-
  

SAT itself. The argument now goes roughly as follows:
>  

box queries to and produces, with non-negligible proba-
Assume and let be any algorithm
bility and for a given input-length, a formula on which
differs from SAT. In the notation we introduce in this paper:

that supposedly solves SAT and that we wish to fool. For a
given formula-size , we run the learning algorithm but use
 
  implies
 bb-pseudo-


   > to answer the equivalence queries against SAT at length
, and also to simulate the oracle in . To be more pre-

 ? 8
cise, the equivalence queries against SAT are simulated by
The bb-pseudo- notation is a natural analogue of the > ?
 @? 
querying about the statement , where is the cir-
pseudo- notation when we want to fool non-uniform algo- cuit for which we ask the equivalence query, and is
rithms with a uniform adversary (see Section 2 for details). the statement in the [6]-proof above. A refined analysis of
the learning algorithm reveals that the result is, either (i) a
Overview of the proof Let us first discuss a simplified >
small set of formulas on which errs, namely those that

box. Assume
  
version of the proof in [6] to see where it fails to be black-
and let be any polynomial-

or the queries to the

simulate the equivalence queries, or their counterexamples,
-oracle, or (ii) a polynomial-size

 



time algorithm that attempts to solve SAT. Let us con- circuit for SAT. If the former case happens infinitely of-

sider the following statement , parameterized by the ten, we are done2. Otherwise, we reach a contradiction be-
formula-size and the algorithm :
   

cause the learned circuits can now be used to solve SAT and
formula  of size such
thus collapse to . An analysis of the learning
There exists
a Boolean

 
 
 and
 !#"and$ 
is%satisfiable,
algorithm very similar to the one we need was observed be-

 either
that,
 
 !
 '& (or , fore by Fortnow, Pavan and Sengupta [5], but their goal was

)* and  has no free variables and
or %
quite different. The authors in [5] ask for further applica-
evaluates to .
 tions of this observation. This may be another. We discuss
the small differences in Section 3.
Here,    +
stands for the result of replacing the first free    Modulo the details, it seems clear that our new proof of
variable ,& 
of by . By our assumption that- , 
the main result in [6] provides a distribution that is com-
>

this statement is true for infinitely many as it asserts that putable with black-box queries to . Indeed, the only use
> 


is incorrect for SAT on formulas of size . Moreover, since
is a polynomial-time algorithm, is an state-


  
. 
  we make of is to answer the equivalence queries by
querying it about a formula of the from for a cir-
 /$@?
?
/$
.
ment, which means that we can construct a polynomial-size cuit , or to answer the queries to the -oracle that have
>
 


 
.
Boolean formula that is satisfiable if and only if nothing to do with . Thus, it is not surprising that the

 is true. Now, let us run on for an
/ / 
$/0

 
  
=A%
argument extends easily to circuits under the assumption
on which the statement is true. If
wrong on . If /
%/ 12 , then is
, then we may run the downward
. This achieves our goal.

self-reducibility of SAT until either we find a satisfying as-

& Discussion about this and previous work Classical


%/ / & 62
signment for , or we find three formulas
% / 3 
% / 5  / 7 /43
, and /45 average-case complexity theory considers problems
on which and , or we find  with a fixed samplable distribution, or as we say, distribu-

%/ .( /
a formula without free variables that evaluates to but tional problems. A distributional problem is average-case


. In either case, we have found a set of at most hard if every efficient algorithm has non-negligible proba-
three formulas on which errs1 . Note, finally, that this
bility of error when the probability is taken over the fixed

/$
.8
procedure is strongly non-black-box on as it needs its de- distribution. Thus, the setting is very different from ours
scription to build the formulas . The same idea with since our distributions may depend on the algorithm.
some additional technicalities gives the proof of (1) and this
is what the authors of [6] did.


A worst-case to average-case reduction is a mapping
from a language to a distributional problem , such that >
Let us now discuss the new proof of (1) that leads to every algorithm B
that has good probability of success on

a sampler that is essentially black-box. The new idea is >can be transformed into an algorithm that solves in the
1 Note that the sizes of the formulas we found may not be , but a clever 9 2 Note again that the size of the formulas may not be . But the same 9
trick devised in [6] takes care of this. trick as before will work.

2
worst-case. The issue of worst-case to average-case reduc-

such that, for every  ,

, we have 
    , B  % ,       
tions may be as old as cryptography itself. We suggest the and for every ,   
 , we have 
 B  ,

.
introduction in [2] for a discussion. The reason we mention

We say that B  is a -algorithm for . A language

, 


this topic here is because there are results showing that cer- belongs to  if there exists a probabilistic polynomial-
B
time algorithm  such that, for every 
B % , 4      
tain worst-case to average-case reductions are impossible if , we have
the reducing algorithm is black-box. Viola [9] proves so 
  , and for every 

, we have , 
=A%


if the reducing algorithm is black-box both in the algorithm B %,

 . A language belongs to if     
B  ? & ? 3 ?
 
and in the hard language . Extending results by Feigen- there exists a family of Boolean circuits and
baum and Fortnow [4], Bogdanov and Trevisan [2] show
a polynomial  
 such that, for every , the size of  is

that, unless the polynomial-time hierarchy collapses, if is
-complete, the reducing algorithm cannot be black-box
bounded
tion of

'  
by 
    , and ?
. It is known that
 
  

 
 computes the characteristic func-
. The
on B
if it makes non-adaptive queries only.

proof of this inclusion is known as Adleman’s argument.
 
  

 
The ‘pseudo’-version of average-case analysis, where More precisely, if is a language in with a -
B

running in time 
    5 
the distribution may depend on the algorithm, has been algorithm , then Adleman’s argu-
studied to a much lesser extent. Several issues are still not ment shows that has Boolean circuits of size ! .
very well understood, and some definitions are not totally
stable yet. In this respect, it is fair to stress that our for- Distributions and samplers We use U  to denote the  
mal definition of black-box adversary has a component that 
uniform probability distribution on   . For every , let
"  . We write "  
"  be a probability distribution on
may be considered not totally black-box. Namely, the ad-
versary needs to know the running time of the algorithm it  to denote the ensemble of distributions
" " 
 $# .
 #&
wants to fool, or the size of the circuits it wants to fool. This 
Let % be a probabilistic algorithm that takes as input and

set aside, the adversary has absolutely no idea of what the 
algorithm does, and in this sense it is black-box. But the
returns a string of length as output. Each
defines a probability distribution %  on
 such   algorithm 
most important feature of the new definition is that it makes ural way: the probability that %& assigns to '(
 the nat-
in
 is 
sense for circuits because a uniform adversary cannot have precisely the probability that % generates ' on input . We  
a non-uniform algorithm built-in in its code. say that a distribution
" " 
 is polynomially samplable
Finally, let us point out that the results in [6] may be if there exists a probabilistic polynomial-time algorithm %
 
"
used to prove our black-box version of (1). Indeed, if the as above such that %)  for every . We say that the



adversary knows that the running time of the algorithm is algorithm % is a polynomial-time sampler. The definition

ahead of time, it can generate 
a distribution that is hard extends naturally to probabilistic oracle algorithms %+* . If
for all algorithms of time simultaneously by choosing %&, runs in polynomial time for every oracle we say that
the code of such an algorithm at random and simulating its %&* is a polynomial-time oracle sampler.
adversary (this requires to have adversaries for machines
that do not conform to any error-gap; see [6, Theorem 2]
for details). It is clear, however, that the same technique Pseudo classes The concept of pseudo complexity classes
fails badly for proving was introduced by Kabanets [7] to model easiness against

  
=A% implies
 bb-pseudo-

  uniform adversaries. The idea is that a language belongs
to the pseudo-version pseudo-- of a complexity class - , if

>
there exists a language in - that is indistinguishable from
because non-uniform algorithms do not have small descrip- by polynomially samplable distributions. Formally:
tions. Thus, the two proofs of (1), the one in [6] and the
new one here, are really different.
class of languages, let


Definition 1 (Pseudo-classes, Kabanets [7]) Let - be a
be a language. We say that


belongs to pseudo-- iff there exists a language in - such >
2 Preliminaries that for every polynomial-time sampler % 3and
'   every
4 poly-
 ,   >  ,    ' 
    . nomial  we have 
.0/12  


 , 
All our languages are over the binary alphabet for all but finitely many .


For a language , we write

for the characteristic func-
 ,     

, is a string not in , then

,
tion of . Thus, if is a string in , then
 , =  ; and if
. All our algorithms are
Let us note here that the definition of pseudo-
by Gotfreund, Shaltiel and Ta-Shma differs from the def-
used

modelled by Turing machines. We assume some familiarity inition of Kabanets in one important aspect: the defini-
with the basic concepts of complexity theory (see [1, 8]).
 
 tion in [6] is stated in terms of the class of probabilistic

Still, we review some. A language belongs to
there exists a probabilistic polynomial-time algorithm
if
B belongs to pseudo 5 -
 

polynomial-time algorithms. In other words, a language
, in the definition of [6], if there

3
exists a probabilistic polynomial-time algorithm such >  Theorem 1 (Bshouty et al. [3]) There exists a probabilis-


 ,   > %, 
3
 4
that for every polynomially samplable distribution % %  
tic polynomial-time oracle algorithm LEARN such that, for
? 
we have  0.0/ 12
,
where the proba-
bility is both over and the internal coin-tosses of . Since >
every circuit
given access to an
with

inputs and size , if LEARN is
-oracle and to an equivalence-oracle
?
    
our goal is to extend the results in [6] to black-box adver- with respect to the Boolean function computed by , then
 ?
saries, we will have to stick to the language view.
 
 LEARN

returns a circuit that is equivalent to with



 
We define now the black-box versions of pseudo-
and pseudo- . As we discussed in the introduction,
probability at least
ability at most .
 
, and returns ‘don’t know’ with prob-

our adversary will be allowed to make oracle calls to only,

 
 >
but he may know the running time of a -algorithm The key question that will lead us to the proof is
>    
the following: what happens to the learning algorithm
for . We formalize this by giving two inputs to an oracle 
 
      
sampler %&* : the input-length , and the running time of LEARN     0
if it is given access to an equivalence-oracle
with respect to a Boolean function

the -algorithm.


Definition 2 A language belongs to bb-pseudo-
 
 iff
that does not have circuits of size ? It is not too hard to see,
 
from the proof of Theorem 1, that in this case, with proba-

> in   
 with a  
 -algorithm running in
for every polynomial-time oracle sampler %* , there exists bility at least , either the algorithm returns a circuit for

of size bigger than , or the collection of all counterex- 

a language
for some
, such for every polynomial   amples generated by the equivalence-oracle is such that for
time   that
>  ,   )4     for all ? , 
? ,      , 
we have 
0.0/ 1  %, every circuit of size there exists an  such that
 %   is the probability distribu- . The reason for this is that LEARN is es-
but finitely many
tion generated by % 
    
  ., where
sentially an approximate halving algorithm that shrinks the
space of consistent size- circuits by a constant factor at
For


A% , the definition is similar where the running each round.
A property very similar to the one we need was also ob-
time is replaced by the size of the circuits.
served by Fortnow, Pavan and Sengupta [5] who gave it a



A% completely different use. The difference between the two
Definition 3 A language belongs to bb-pseudo- 
 &
properties is on the assumption: in [5] they assume that
> 

A%
iff for every polynomial-time oracle sampler %* , there ex-  does not have circuits of size , and conclude that the
ists a language
 in with circuits for size
'  collection of counterexamples rules out every size- circuit.
8 
 ,   > %, 
 every4 polynomial    '  
for some , such that 3for we have We do not make any

0.0/1   for all but finitely  assumption and conclude that, with
  3
probability at least , either the algorithm returns a good
many , where %) is the probability distribution generated
      
  . circuit of size at most , or the counterexamples rule out
by %
every size- circuit. Our property is only slightly stronger
and has essentially the same proof. Let us encapsulate the


Let us also recall the i.o. quantifiers. Let - be a class of
languages. We say that belongs to i.o.-- if there exists a
exact observation that we need in a lemma:
           


language >  >
    in - and
  there 
0  exist infinitely many such that Lemma 1 Let be a Boolean function
.

and let be an integer. Then, if LEARN is given access to
an oracle and to an equivalence-oracle with respect
3 Learning circuits  
to , and if denotes the collection of all counterexam-

     
ples generated by the equivalence-oracle in an execution of
 
    
LEARN , then, with probability at least over the

  3
The proof of our main result builds on the celebrated internal coin-tosses, either LEARN returns a circuit
 ?
? ,     %, 
learning algorithm of Bshouty et al. for learning circuits. for of size at most , or for every circuit of size ,
We discuss this algorithm in this section. We also state and there exists an ( such that ,  .
prove the main property we need about it.


We say that an algorithm is given access to an

 ,    ,   
Proof sketch: The algorithm LEARN produces a collection
 " ! 
   
    
equivalence-oracle with 
respect to

a Boolean function
if has the right to pose queries of the
of pairs
Having built

inductively
# "
as follows. Initially,
 , &   %, &        ,$"   % ,$"  
.
, the al-
form: ‘Does circuit % compute ?’ The equivalence-oracle  
gorithm proceeds to extend it by one more pair. Using the

&      &%
answers faithfully either ‘yes’ or ‘no’ in unit time, and in -oracle and its randomness, LEARN samples a collec-
,
% ,      , 
case it answers ‘no’ it also provides a counterexample tion of circuits % % , each of size , independently
such that % . The result can be stated as fol- and approximately uniformly at random from the collection
lows:
of all circuits of size that are consistent with the current

4
 " . Then it forms the circuit % that combines % % & % 1.   %  is true;
by putting a majority gate on top, and queries it to the equiv- 2.

  % is satisfiable;
alence oracle. If the equivalence-oracle says that % com-

putes , the algorithm stops. Otherwise, the equivalence- 3. % . does not compute SAT on Boolean formulas of size
oracle provides a counterexample
. The crux of the ," &
argument is that % &      &%
% are approximately uniformly
distributed among the circuits of size that are consistent Proof : The equivalence of (1) and (2) follows from the
"
with , so a counterexample to % is very likely to be a
Cook-Levin reduction. Let us show the equivalence of (1)
and (3). If % computes SAT on Boolean formulas of size
  
counterexample to a constant fraction of the circuits of size  , it is clear that %   
is false. Conversely, if % does not
. It follows that after  rounds, there is a good 
chance that either we produced a circuit for , or there are  
compute SAT on Boolean formulas of size , then either it
 

no size- circuits that are consistent with  (see [3] and [5]  returns on a satisfiable formula , or it returns on an

  
unsatisfiable formula . In the former case, we are done
for details). 
because % is true. In the latter case, consider the value 
of % on  !#"  
 &
      
and . If both are , we are done be-
cause % is true. Otherwise, we set for the     '+
4 Alternative and stronger proof one that gives and recurse. Since is unsatisfiable, both 
   "
and    '&
are unsatisfiable as well. Now, if the
In this section we present an alternative proof to the

recursion reaches a formula in which all variables are set,
  
main result in [6]. In fact, our argument proves something
stronger. This will lead to our main result about .

  necessarily evaluates to yet % returns on . Hence
  
% is true. 
We start with the statement of the black-box version of the
main result in [6], which is what our argument proves: The following lemma is already very close to our goal

of proving Theorem 2. If is a set of formulas and is >
Theorem 2
>  
  
    
 >  ,   
language, we say that fails to solve SAT on when there
implies bb-pseudo- exists a formula  such that , 
SAT .  ,
  

 Lemma 3 If SAT 

  
Before we get into the proof, we need some preparations. , then there exists a probabilistic

>  
  

For a circuit % with inputs, let % be the following polynomial-time oracle algorithm * such that, for every
statement: language in with a -algorithm running in 
formula  of size such

   
time , there exist infinitely many such that the algorithm
  returns, with probability at least
There exists a Boolean
% %
   
 on input and
that, .
% %
  and
either
% 
 
   
and
#" .  % is
satisfiable,
   & . or , 
, a set of Boolean formulas on which fails to solve >
or % 
   and  has no free variables and SAT.

Proof : Let us assume SAT 
  

. The algorithm * , on


evaluates to .
  
inputs  and  , starts simulating the algorithm LEARN
By an appropriate encoding of Boolean formulas, we may   
on inputs  and 
with an equivalence-oracle for SAT.
assume that the sizes of  
!'+
and are the same. One 
way to do this is by saving a couple of bits next to the encod- That is, the learning algorithm is allowed to ask queries of
ing of each propositional variable of to encode the fact  the form: ‘Is % a circuit that computes SAT on formulas of

that a variable has been instantiated or not, and by which size .’ Since this strong equivalence-oracle is not avail-

 
  
value if so. able, we will have to show how to simulate it using the
It is clear that % is decidable in when given oracle we do have. Similarly, the oracle that LEARN
% as input. By the Cook-Levin reduction, there exists a uses is not available, so we simulate it as well. The idea is
polynomial-time computable function  that, given a circuit
 # 
that we pretend that the oracle we have correctly solves SAT

% with inputs and size , returns a Boolean formula  % despite we know it doesn’t.


     
that has size polynomial in and and is satisfiable if and We may assume that the -oracle that LEARN uses is
only if % is true. Let  -oracle a query  , we
be the size of the formula
returned by  when it is given a circuit with inputs and
 SAT. Whenever LEARN asks its

add  to the set , and we answer the query by using the or-

size . We may assume the size of  % # 
is the same for 
acle we have instead of SAT. This is all for the simulation of
each such % . the -oracle. Note that the oracle we have may be com-
 pletely wrong on  , but we do not care and proceed with the
Lemma 2 Let % be a Boolean circuit with inputs. Then, simulation of LEARN anyway. Now we turn to the simula-
the following are equivalent: tion of the equivalence-oracle. Whenever LEARN asks an

5
equivalence query % , we compute the formula  % /  # 
   
is satisfiable, run the downward self-reducibility of SAT to
expressing the statement % and query it to the oracle we produce a satisfying assignment for ; if we succeed, we 
have. If the answer to is , then our oracle claims that / / accept, otherwise, we  reject. Assuming that the probability  
is unsatisfiable, so it claims that % computes SAT on formu-
 /    <<
of (1) is at least for all but finitely many , this is an
las of size . In this case we add to and proceed with    algorithm that solves SAT with error bounded by
for all but finitely many . It follows that SAT 
  


the simulation of LEARN. On the other hand, if the answer
/
,
to the query is , then our oracle claims that is satisfi- which contradicts the hypothesis. 
able, so it claims that % does not compute SAT on formulas
  4
Hence, there exist infinitely  many  for which the proba-  2  

of size . Then we start the downward self-reducibility of
SAT searching for a satisfying assignment to but using /
bility of (2) is at least 
algorithm running in time , so has
 . But has a -
-size circuits by
 > 5 >
our oracle instead of SAT. If the search succeeds, we have a
Boolean formula of size witnessing % . This means     
Adleman’s argument. From this we conclude that there ex-  >

that is a counterexample to the equivalence query % with
ist infinitely many for which differs from SAT on some
formula in with probability at least  
. This contradicts

respect to SAT and the simulation of LEARN can proceed. the assumption and the proof is over.  (of claim and of
If the search does not succeed, the we produced a set of at lemma)
most three formulas that constitutes a flagrant proof that our
oracle does not compute SAT. We add them to and stop.  A second look at the proof of Lemma 3 reveals that every
After polynomially many steps, LEARN either produces  
formula in is of one of the following types: either it is
a circuit % or says ‘don’t know’. In the first case we add query  to the
/  #  # 
-oracle (which we assumed to be SAT),
 
 &
 % to . In the latter, we add to the collection of or it is a formula of the form  % , where % is a Boolean
all counterexamples  that have been generated in
the simulation. This concludes the construction of * . The

circuit, or it is a counterexample to an equivalence query 
and is hence a formula of size . By appropriate padding, 
correctness will follow from the next claim: we may assume that the formulas of the types  and  %  
>  
  
 have exactly the same size. Let us say this size is
some constant that depends only on the running time of
for
Claim 1 Let be a language in with a -      
  . This gives a collection of formulas of

algorithm running in time . Then, there exists infinitely
  produces, with probability
    LEARN

    
many such that
 


sizes or . We can also bound the size of by the
at least , a set on which fails to solve SAT. > running time of
the algorithm * . Let us say that the size


of is at most for some constant  that depends only

Proof of claim: Suppose on the contrary that, for all but
> on the running time of the algorithm LEARN. This will be
  
finitely many , the probability that fails to solve SAT on useful for the next proof.
is less than

 because when-
. This means that the simulation of LEARN
  

  


reaches the end with probability at least
Proof of Theorem 2: Suppose SAT  . We show
> 
ever we stop the simulation prematurely is because we have
that SAT  bb-pseudo- . Let * be the algorithm of
found a flagrant proof that SAT and we have added the
Lemma 3. Consider the sampling algorithm % * that,

witnesses to . Note that when we reach the end, either we  
 , runs *
   
and *
  on   in-

  
     
produce a circuit, or add the collection of all counterexam- 
puts and
  , , or.  & 

ples to . We claim that for all but finitely many , with
 
 . Let be the collection of all such formulas that have
This may produce a set of

formulas of sizes
probability at least  , the simulation of LEARN produces   
 
1. either a circuit for SAT on formulas of length ,
 size . The cardinality of is bounded by
we choose one formula uniformly at random in this set and
. Then

5
2. or a collection of formulas  on which every circuit of
output it.
Let us now argue that this sampling algorithm does what
size fails to solve SAT.
we want. We follow essentially the same reasoning as in
>  
  

Indeed, if all oracle answers were correct, the probability   
[6]. Let be a language in
   a
with 
-algorithm
' 

that both (1) and (2) fail would be bounded by by running in time . Let  . By Lemma 3, 

Lemma 1. Since the probability  that some oracle answer    
there exist infinitely many for which the algorithm
inputs  and  returns, with probability at least

on

is incorrect is bounded by

, it follows that both (1) and
      set  of formulas on which fails to solve SAT. Call such
,a
>
(2) fail with probability at most .   ’s useful. Consider now the following two events: (i) 

Now, let us argue that there exist infinitely many such  of size and (ii)  contains some

that the probability of (1) is less than
could solve SAT in 
. Otherwise we
 

contains some formula  

   
as follows: given a formula of
  , and take the resulting circuit, if
formula of size . On a useful , at least one of these two  
size , run
any, to decide the satisfiability of ; if the answer is that  
events must have probability at least
infinitely many , the probability that either

. Therefore, for
 
      

6

              

 
or
> 
   of size on which
outputs a
formula i.o.-bb-pseudo- . Unfortunately, the proof does not
fails to solve SAT is at least 
. Hence, there exist
infinitely many lengths , on which the sampler % 
seem to go through directly. In fact, everything works fine

'  
fools except when we want to take care of the fact that the sam-
>
with probability at least  . pler from Lemma 3 may return formulas of different sizes.

   
was to consider the execution of * on
  and     and keep only those formulas of
   
The trick we used
To close this section, let us point out that we did not

make any effort to optimize the probability that the ad-
 &
size that it produces, if any. The problem 
 is
that the hard
instance it produces may be of sizes  or , but not of
versary will find a counterexample. We are satisfied with
non-negligible probability. This should be contrasted with

size . Perhaps a padding argument could fix this, but we
 
the results in [6] where a counterexample is produced with do not see exactly how.
   

constant probability . Let us also remark that the hy-
  
pothesis in Theorem 2 may be replaced by
 . Indeed, by standard gap-amplification argu- 6 Conclusions and Open Problems
ments and the downward self-reducibility of SAT, it is not
hard to show that both conditions are equivalent. The most natural black-box version of Definition 1 is ar-
guably the following:
5 Main result


Definition 4 (Revised black-box pseudo-classes) Let
The bulk of the argument for our main result was ex-
say that


- be a class of languages, let be a language. We
belongs to strong-bb-pseudo-- iff for every
posed already in the proof of Theorem 2. As a matter of
polynomial-time oracle sampler % * , there exists a lan-
> ' 
 
 , $ >  ,  (
fact, the proof is now even easier because we do not have to
guage in - such that3 for every
4 polynomial 
   we have
worry about the possibility that the learning algorithm may

.0/ 1   for all but finitely
sometimes work! In other words, it is immediate that case
(1) in Claim 1 cannot occur for almost all .
 many .

Theorem 3 Note the important switch of quantifers between Defini-

 
=A% implies
  bb-pseudo-

=A%  tion 1 and Definition 4 and the absence of running times.
We do not know if our results in Theorem 2 and Theorem 3
 
  are true under this new notion, or if there is a good reason


Proof : Assume SAT  . Consider the oracle algo-
rithm * from Lemma 3. The new version of Claim 1 is the
why this is not possible. It would be nice to understand
these issues better. On the one hand, it is true that Defini-
following:

> 
  tion 4 captures the pure essence of a black-box adversary.

Claim 2 Let 
be a language in with circuits  But on the other, providing the running time of the algo-

      
of size . Then, there exist infinitely many on which
  produces, with probability at least  , a set 
rithm to the adversary is not giving him much information.


 
This is particularly clear in the case of bb-pseudo-  
 >
on which fails to solve SAT. because there are exponentially many circuits of size .
At the end of Section 5 we discussed the i.o. versions of
Proof of claim: The proof proceeds as in Claim 1 until we  our results and why the current proof does not seem to work.

argue that the probability of (1) cannot be at least for It ought to be possible to fix this by some sort of padding
all but finitely many . Something stronger is true here: argument but we do not see how. A final issue we have


the probability of (1) cannot be positive for all but finitely 
not investigated is the analogue of these results for co-
many because SAT does not have polynomial-size circuits.
It follows that there exist infinitely many on which the
 is easy to find the hard instances to any co-

languages. Is it true that if SAT is not in co- then it
-algorithm?

probability of (2) is at least  ; contradiction.  (of claim) This may be relevant for propositional proof complexity.

  Acknowledgments: I want to thank Ricard Gavaldà for

 
A more careful analysis reveals that we can put
in Claim 2. Also, the algorithm * on input
in-

 providing feedback at an early stage of this work, and the
stead of
and   
need not run LEARN  
as LEARN   
      referees of CCC 2006 for the useful comments.

suffices. The rest of the proof of Theorem 3 mimics the

proof of Theorem 2, and we are done.  (of theorem) References

and show that if i.o.-

 
Next we would like to extend our results to i.o. classes
, then

    [1] J. L. Balcázar, J. Dı́az, and J. Gabarró. Structural Com-
plexity I. Springer-Verlag, second edition, 1996.

7
[2] A. Bogdanov and L. Trevisan. On worst-case to
average-case reductions for NP problems. In 44th An-
nual IEEE Symposium on Foundations of Computer
Science, 2003.
[3] N. H. Bshouty, R. Cleve, R. Gavaldà, S. Kannan, and
C. Tamon. Oracles and queries that are sufficient for
exact learning. Journal of Computer and System Sci-
ences, 52:421–423, 1996.
[4] J. Feigenbaum and L. Fortnow. On the random-self-
reducibility of complete sets. SIAM Journal of Com-
puting, 22:994–1005, 1993.
[5] L. Fortnow, A. Pavan, and S. Sengupta. Proving SAT
does not have Small Circuits with an Application to the
Two-Queries Problem. In 18th IEEE Conference on
Computational Complexity, pages 347–357, 2003.
[6] D. Gutfreund, R. Shaltiel, and A. Ta-Shma. If NP Lan-
guages are Hard on the Worst-Case Then It is Easy to
Find Their Hard Instances. In 20th IEEE Conference
on Computational Complexity, pages 243–257, 2005.
[7] V. Kabanets. Easiness assumptions and hardness tests:
Trading time for zero error. Journal of Computer and
System Sciences, 62(2):236–252, 2001. A preliminary
version appeared in CCC 2000.
[8] C. H. Papadimitriou. Computational Complexity.
Addison-Wesley, 1995.
[9] E. Viola. The complexity of constructing pseudoran-
dom generators from hard functions. Journal of Com-
putational Complexity, 13(3-4):147–188, 2004. A pre-
linary version appeared in CCC 2003 under the title
‘Hardness vs. Randomness within Alternating Time’.