<p>Razborov and Rudich's result in their <a href="http://www.cs.cmu.edu/~rudich/papers/natural.ps">natural proofs paper</a> 
is quite general. It is not restricted to $\mathsf{P}$ vs. $\mathsf{NP}$.</p>

<p>I personally like the clarity of the explanation in <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/">Stasys Jukna</a>'s recent book "<a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/">Boolean Function Complexity: Advances and Frontiers</a>":</p>

<blockquote>
  <p>Definition 18.30. A function $G : \{0,1\}^l \to \{0,1\}^n$ with $l &lt; n$ is called an $(s,\epsilon)$-secure pseudorandom generator if for any circuit $C$ of size $s$ on $n$ variables,
  $$|Pr[C(y) = 1] − Pr[C(G(x)) = 1]| &lt; \epsilon,$$
  where $y$ is chosen uniformly at random in $\{0,1\}^n$, and $x$ in $\{0,1\}^l$.</p>
  
  <p>Definition 18.31. Let $f : {0,1}^n \to {0,1}$ be a boolean function. 
  We say that $f$ is $(s,\epsilon)$-hard if for any circuit $C$ of size $s$,
  $$|Pr[C(x) = f(x)] − \frac{1}{2}| &lt; \epsilon,$$
  where $x$ is chosen uniformly at random in $\{0,1\}^n$.  </p>
  
  <p>A pseudo-random function generator is a boolean function $f(x,y) : \{0,1\}^{n+n^2} \to \{0,1\}$. By setting the $y$-variables at random, we obtain its random subfunction $f_y(x) = f(x,y)$. Let $h : \{0,1\}^n \to \{0,1\}$ be a truly random boolean function. A generator $f(x,y)$ is secure against $\Gamma$-attacks if for every circuit $C$ in $\Gamma$,
  $$|Pr[C(f_y) = 1] − Pr[C(h) = 1]| &lt; 2^{−n^2}.$$</p>
  
  <p>A $\Gamma$-natural proof against $\Lambda$ is a property $\Phi : B_n \to {0,1}$ satisfying the following three conditions:<br>
  1. Usefulness against $\Lambda$ : $\Phi(f) = 1$ implies $f \notin \Lambda$.<br>
  2. Largeness: $\Phi(f) = 1$ for at least $2^{−O(n)}$ fraction of all $2^{2^n}$ functions $f \in B_n$.<br>
  3. Constructivity: $\Phi \in \Gamma$, that is, when looked at as a boolean function in $N = 2^n$ variables, the property $\Phi$ itself belongs to the class $\Gamma$.  </p>
  
  <p>Theorem 18.35. If a complexity class $\Lambda$ contains a pseudo-random function generator that is secure against Γ-attacks, then there is no $\Gamma$-natural proof against $\Lambda$.</p>
</blockquote>

<p>The question are: 
1. Do we believe if there are such hard functions?
2. How constructive/large do we expect the properties in 
currently possible separation proofs to be?</p>

<p>On the other direction, Razbarov has mentioned in various places that 
he personally views the result as guide for what to avoid and 
not as an essential obstacle to proving lower-bounds.</p>

<p>Apart from <a href="http://www.cs.cmu.edu/~ryanw/">Ryan Williams</a>'s papers during the last few years there were two papers that he has mentioned:</p>

<ol>
<li><p><a href="http://www-math.mit.edu/~tchow/">Timothy Chow</a>, "<a href="http://www-math.mit.edu/~tchow/almost.pdf">Almost Natural Proofs</a>", 2008, which states that if we relax the largeness a little bit then there are provably natural properties that would separate $\mathsf{NP}$ from $\mathsf{P}$.</p></li>
<li><p><a href="http://www.cs.rutgers.edu/~allender/">Eric Allender</a> and <a href="http://www.math.cas.cz/~koucky/">Michal Koucký</a>, "<a href="http://ftp.cs.rutgers.edu/pub/allender/amplifying.pdf">Amplifying Lower Bounds by Means of Self-Reducibility</a>", 2008, which says that to separate $\mathsf{NC^1}$ from $\mathsf{TC^0}$ we only need to prove slightly superlinear lower-bounds on the size of $\mathsf{TC^0}$ circuits computing the Boolean Formula Evaluation problem. The existence of natural proofs for such a lower-bound does not seem to be unreasonable.</p></li>
</ol>

<p>Relativization and Algebraization are bit more tricky and dependent on the way we define the relaztivization for these classes. But as a general rule <em>simple</em> diagonalization (a diagonalization which uses the same counter-example for all machines computing the same function, i.e. the counter-example only depends on what machines in the smaller compute and does not depend on their code and how they compute) cannot separate these classes.</p>

<p>It is possible to extract non-simple diagonalization functions from indirect diagonaliztion results like time-space lower-bounds for SAT.</p>

CC BY-SA 3.0
2013-10-08T18:28:37.467Z
".... that is secure against Γ-attacks" is this same as OWFs in $P$ vs $NP$ as when we compare say $L$ vs $NL$ or $NP$ vs $coNP$ or $PH$ vs $PSpace$?
Turbo
CC BY-SA 3.0
2013-10-08T18:37:45.260Z
SO you imply that circuits in $NP$, $CoNP$, $PH$ and $PSPACE$ all cannot break the OWF in the class which  we are considering them against (for example in $NP$ Vs $CoNP$ circuits in CoNP cannot break OWFs in NP)? Is this interpretation correct? One question to complete the loop. Does $L$ have PNGs?
Turbo
CC BY-SA 3.0
2013-10-08T18:44:33.847Z
$\Gamma$ determines the amount of constructivity you want from the proof not the larger class.
Kaveh
CC BY-SA 3.0
2013-10-08T18:52:37.050Z
@JAS, btw, if I were you I would not accept an answer so quickly, you might get better answers.
Kaveh
CC BY-SA 3.0
2013-10-08T18:54:33.627Z
oh ok.... I am unsure what better can be given other than what is in the book though.
Turbo
CC BY-SA 3.0
2013-10-08T18:56:25.253Z
@JAS, it is a very good book, but you might also get perspectives about the topic from others.
Kaveh
CC BY-SA 3.0
2013-10-08T18:12:41.587Z
2013-10-08T18:41:43.277Z
2013-10-08T18:41:43.277Z
Kaveh
<p>There are (at least) two areas where existing barriers have little to say:</p>

<p><strong>ACC Lower Bounds</strong> There is no known barrier to proving that TC0 is not in (non-uniform) ACC -- other than the possibility that the separation may be false. It's unclear whether the Natural Proofs barrier should apply to ACC. The question boils down to: should we expect there to be pseudorandom functions implementable in ACC?</p>

<p><strong>LOGSPACE vs NP</strong> As pointed out by <a href="http://people.cs.uchicago.edu/~fortnow/papers/diag.pdf" rel="nofollow">Fortnow</a>, the existing oracle mechanisms for space-bounded computation do not seem to present a real barrier to LOGSPACE vs NP. To my knowledge, the known oracle models which yield a collapse of LOGSPACE and NP also collapse ALTERNATING LOGSPACE (i.e., P) and ALTERNATING POLYTIME (i.e., PSPACE), hence these oracles treat alternating computational models inconsistently with reality (since LOGSPACE is not equal to PSPACE). </p>

CC BY-SA 3.0
2013-10-08T21:02:39.507Z
2013-10-09T12:41:11.260Z
2013-10-09T12:41:11.260Z
Ryan Williams
<p>Do <a href="http://en.wikipedia.org/wiki/Natural_proof">Natural Proofs</a>, Relativization and Algebrization also affect separation of other complexity classes like $L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$ etc?</p>

<p>For instance natural proofs barrier should affect any proof of $NP\neq CoNP$ since it will separate $P\neq NP$. However relation between $NP$ and $CoNP$ does not seem to have much with OWFs as compared to relation between $P$ and $NP$. So do natural proofs affect the stronger separation of $NP\neq CoNP$?</p>

CC BY-SA 3.0
2013-10-08T17:53:22.480Z
I know the top line of the paper(http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf) has $P\neq PSPACE$, $P\neq NP$, $P\neq NC$. That is why I excluded $P$ from the list above. Since I klnow $NP\neq CoNP$ spearates $P$ and $NP$ also I included the question separately. So do you have a quote where it says specifically $NP\neq CoNP$?
Turbo
CC BY-SA 3.0
2013-10-08T18:50:14.447Z
Possibly related: [Advanced techniques for determining complexity lower bounds](http://cstheory.stackexchange.com/questions/18426)
Kaveh
<cc.complexity-theory><barriers>
Barriers to separating other complexity classes
Turbo
# Barriers to separating other complexity classes

(Asked by: username_0 on 2013-10-08)

Do [Natural Proofs](http://en.wikipedia.org/wiki/Natural_proof), Relativization and Algebrization also affect separation of other complexity classes like $L\neq NL\neq NP\neq coNP \neq PH\neq PSPACE$ etc?

For instance natural proofs barrier should affect any proof of $NP\neq CoNP$ since it will separate $P\neq NP$. However relation between $NP$ and $CoNP$ does not seem to have much with OWFs as compared to relation between $P$ and $NP$. So do natural proofs affect the stronger separation of $NP\neq CoNP$?

**Tags:** cc.complexity-theory, barriers

> **Comments:**
> **username_0**: I know the top line of the paper(http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf) has $P\neq PSPACE$, $P\neq NP$, $P\neq NC$. That is why I excluded $P$ from the list above. Since I klnow $NP\neq CoNP$ spearates $P$ and $NP$ also I included the question separately. So do you have a quote where it says specifically $NP\neq CoNP$?  
> **username_1**: Possibly related: [Advanced techniques for determining complexity lower bounds](http://cstheory.stackexchange.com/questions/18426)  

---

## 2 answers

### Answer by username_2 on 2013-10-08. Score: 13 | Accepted answer

There are (at least) two areas where existing barriers have little to say:

**ACC Lower Bounds** There is no known barrier to proving that TC0 is not in (non-uniform) ACC -- other than the possibility that the separation may be false. It's unclear whether the Natural Proofs barrier should apply to ACC. The question boils down to: should we expect there to be pseudorandom functions implementable in ACC?

**LOGSPACE vs NP** As pointed out by [Fortnow](http://people.cs.uchicago.edu/~fortnow/papers/diag.pdf), the existing oracle mechanisms for space-bounded computation do not seem to present a real barrier to LOGSPACE vs NP. To my knowledge, the known oracle models which yield a collapse of LOGSPACE and NP also collapse ALTERNATING LOGSPACE (i.e., P) and ALTERNATING POLYTIME (i.e., PSPACE), hence these oracles treat alternating computational models inconsistently with reality (since LOGSPACE is not equal to PSPACE).


---

### Answer by username_1 on 2013-10-08. Score: 7

Razborov and Rudich's result in their [natural proofs paper](http://www.cs.cmu.edu/~rudich/papers/natural.ps)
is quite general. It is not restricted to $\mathsf{P}$ vs. $\mathsf{NP}$.

I personally like the clarity of the explanation in [Stasys Jukna](http://www.thi.informatik.uni-frankfurt.de/~jukna/)'s recent book "[Boolean Function Complexity: Advances and Frontiers](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/)":

> Definition 18.30. A function $G : \{0,1\}^l \to \{0,1\}^n$ with $l < n$ is called an $(s,\epsilon)$-secure pseudorandom generator if for any circuit $C$ of size $s$ on $n$ variables,
> $$|Pr[C(y) = 1] − Pr[C(G(x)) = 1]| < \epsilon,$$
> where $y$ is chosen uniformly at random in $\{0,1\}^n$, and $x$ in $\{0,1\}^l$.
>
> Definition 18.31. Let $f : {0,1}^n \to {0,1}$ be a boolean function.
> We say that $f$ is $(s,\epsilon)$-hard if for any circuit $C$ of size $s$,
> $$|Pr[C(x) = f(x)] − \frac{1}{2}| < \epsilon,$$
> where $x$ is chosen uniformly at random in $\{0,1\}^n$.
>
> A pseudo-random function generator is a boolean function $f(x,y) : \{0,1\}^{n+n^2} \to \{0,1\}$. By setting the $y$-variables at random, we obtain its random subfunction $f\_y(x) = f(x,y)$. Let $h : \{0,1\}^n \to \{0,1\}$ be a truly random boolean function. A generator $f(x,y)$ is secure against $\Gamma$-attacks if for every circuit $C$ in $\Gamma$,
> $$|Pr[C(f\_y) = 1] − Pr[C(h) = 1]| < 2^{−n^2}.$$
>
> A $\Gamma$-natural proof against $\Lambda$ is a property $\Phi : B\_n \to {0,1}$ satisfying the following three conditions:  
> 1. Usefulness against $\Lambda$ : $\Phi(f) = 1$ implies $f \notin \Lambda$.  
> 2. Largeness: $\Phi(f) = 1$ for at least $2^{−O(n)}$ fraction of all $2^{2^n}$ functions $f \in B\_n$.  
> 3. Constructivity: $\Phi \in \Gamma$, that is, when looked at as a boolean function in $N = 2^n$ variables, the property $\Phi$ itself belongs to the class $\Gamma$.
>
> Theorem 18.35. If a complexity class $\Lambda$ contains a pseudo-random function generator that is secure against Γ-attacks, then there is no $\Gamma$-natural proof against $\Lambda$.

The question are:
1. Do we believe if there are such hard functions?
2. How constructive/large do we expect the properties in
currently possible separation proofs to be?

On the other direction, Razbarov has mentioned in various places that
he personally views the result as guide for what to avoid and
not as an essential obstacle to proving lower-bounds.

Apart from [username_2](http://www.cs.cmu.edu/~ryanw/)'s papers during the last few years there were two papers that he has mentioned:

1. [Timothy Chow](http://www-math.mit.edu/~tchow/), "[Almost Natural Proofs](http://www-math.mit.edu/~tchow/almost.pdf)", 2008, which states that if we relax the largeness a little bit then there are provably natural properties that would separate $\mathsf{NP}$ from $\mathsf{P}$.
2. [Eric Allender](http://www.cs.rutgers.edu/~allender/) and [Michal Koucký](http://www.math.cas.cz/~koucky/), "[Amplifying Lower Bounds by Means of Self-Reducibility](http://ftp.cs.rutgers.edu/pub/allender/amplifying.pdf)", 2008, which says that to separate $\mathsf{NC^1}$ from $\mathsf{TC^0}$ we only need to prove slightly superlinear lower-bounds on the size of $\mathsf{TC^0}$ circuits computing the Boolean Formula Evaluation problem. The existence of natural proofs for such a lower-bound does not seem to be unreasonable.

Relativization and Algebraization are bit more tricky and dependent on the way we define the relaztivization for these classes. But as a general rule *simple* diagonalization (a diagonalization which uses the same counter-example for all machines computing the same function, i.e. the counter-example only depends on what machines in the smaller compute and does not depend on their code and how they compute) cannot separate these classes.

It is possible to extract non-simple diagonalization functions from indirect diagonaliztion results like time-space lower-bounds for SAT.

> **Comments:**
> **username_0**: ".... that is secure against Γ-attacks" is this same as OWFs in $P$ vs $NP$ as when we compare say $L$ vs $NL$ or $NP$ vs $coNP$ or $PH$ vs $PSpace$?  
> **username_0**: SO you imply that circuits in $NP$, $CoNP$, $PH$ and $PSPACE$ all cannot break the OWF in the class which  we are considering them against (for example in $NP$ Vs $CoNP$ circuits in CoNP cannot break OWFs in NP)? Is this interpretation correct? One question to complete the loop. Does $L$ have PNGs?  
> **username_1**: $\Gamma$ determines the amount of constructivity you want from the proof not the larger class.  
> **username_1**: @JAS, btw, if I were you I would not accept an answer so quickly, you might get better answers.  
> **username_0**: oh ok.... I am unsure what better can be given other than what is in the book though.  
> **username_1**: @JAS, it is a very good book, but you might also get perspectives about the topic from others.  

---

