<p>As Damiano Mazza points out in his comment, the barrier of natural proofs does not render the study of circuit complexity useless. Rather, it only rules out one family of proofs.</p>
<p>By now there are several examples of lower bounds that were proved using non-natural proofs. Here are two examples:</p>
<ul>
<li><p>All proofs that use diagonalization (such as <a href="https://people.csail.mit.edu/rrw/acc-lbs.pdf" rel="noreferrer">Ryan Williams' celebrated proof</a> that <span class="math-container">$\mathbf{NEXP} \not\subseteq \mathbf{ACC^0}$</span>) are non-natural.</p>
</li>
<li><p>The <a href="http://www.math.ias.edu/%7Eavi/PUBLICATIONS/KarchmerRaWi1995.pdf" rel="noreferrer">KRW conjecture</a>, if proved, would yield lower bounds via a non-natural proof (even if the conjecture itself would be proved using natural proofs).</p>
</li>
</ul>

CC BY-SA 4.0
2023-01-18T23:12:38.710Z
Also worth pointing out that $NEXP \not\subseteq ACC^0$ uses lots of circuit results within the proof, so those circuit results certainly weren't useless! It's just the proof *also* uses diagonalization, which is how it gets around being Razborov-Rudich natural.
Joshua Grochow
CC BY-SA 4.0
2023-01-18T11:55:00.967Z
2023-01-18T13:07:35.930Z
2023-01-18T13:07:35.930Z
Or Meir
<p>Apparently boolean function complexity analysis through circuit complexity has a limit (as they are natural proofs), and this means it is not possible to proof <span class="math-container">$P \not= NP$</span> unless there are no one-way functions using circuit complexity techniques.</p>
<p>I'm interested on knowing how is this field (if so) being developed nowadays and what would be the motivation for it if either way no technique would be able to solve <span class="math-container">$P$</span> vs <span class="math-container">$NP$</span></p>

CC BY-SA 4.0
2023-01-17T08:16:25.070Z
I am not an expert, but saying that "no technique [using Boolean circuits] would be able to solve $P$ vs $NP$" is certainly an overstatement.  A natural proof is a particular kind of lower bound proof about Boolean circuits which is known to be unlikely to yield lower bounds strong enough to separate $\mathsf P$ from $\mathsf{NP}$, but not every lower bound proof is bound to be natural.  Separating complexity classes is definitely still possible, in theory, via Boolean circuit lower bounds established through non-natural proofs.
Damiano Mazza
CC BY-SA 4.0
2023-01-18T23:15:56.317Z
As others have mentioned, Razborov-Rudich only rules out a certain *kind* of proof that uses circuits. One way of making precise the limitations of the natural proofs barrier is Timothy Chow's [Almost Natural Proofs](https://doi.org/10.1016/j.jcss.2010.06.017), which shows that if one weakens the parameters in Razborov-Rudich slightly, then such "almost natural proofs" do exist, assuming the same pseudorandomness hypothesis as in Razborov-Rudich.
Joshua Grochow
<circuit-complexity><boolean-functions>
Value of studying boolean function complexity through circuits complexity nowadays
Wilmer Bandres Hernández
# Value of studying boolean function complexity through circuits complexity nowadays

(Asked by: username_0 on 2023-01-16)

Apparently boolean function complexity analysis through circuit complexity has a limit (as they are natural proofs), and this means it is not possible to proof $P \not= NP$ unless there are no one-way functions using circuit complexity techniques.

I'm interested on knowing how is this field (if so) being developed nowadays and what would be the motivation for it if either way no technique would be able to solve $P$ vs $NP$

**Tags:** circuit-complexity, boolean-functions

> **Comments:**
> **username_1**: I am not an expert, but saying that "no technique [using Boolean circuits] would be able to solve $P$ vs $NP$" is certainly an overstatement.  A natural proof is a particular kind of lower bound proof about Boolean circuits which is known to be unlikely to yield lower bounds strong enough to separate $\mathsf P$ from $\mathsf{NP}$, but not every lower bound proof is bound to be natural.  Separating complexity classes is definitely still possible, in theory, via Boolean circuit lower bounds established through non-natural proofs.  
> **username_2**: As others have mentioned, Razborov-Rudich only rules out a certain *kind* of proof that uses circuits. One way of making precise the limitations of the natural proofs barrier is Timothy Chow's [Almost Natural Proofs](https://doi.org/10.1016/j.jcss.2010.06.017), which shows that if one weakens the parameters in Razborov-Rudich slightly, then such "almost natural proofs" do exist, assuming the same pseudorandomness hypothesis as in Razborov-Rudich.  

---

## 1 answers

### Answer by username_3 on 2023-01-18. Score: 5

As username_1 points out in his comment, the barrier of natural proofs does not render the study of circuit complexity useless. Rather, it only rules out one family of proofs.

By now there are several examples of lower bounds that were proved using non-natural proofs. Here are two examples:

* All proofs that use diagonalization (such as [Ryan Williams' celebrated proof](https://people.csail.mit.edu/rrw/acc-lbs.pdf) that $\mathbf{NEXP} \not\subseteq \mathbf{ACC^0}$) are non-natural.
* The [KRW conjecture](http://www.math.ias.edu/%7Eavi/PUBLICATIONS/KarchmerRaWi1995.pdf), if proved, would yield lower bounds via a non-natural proof (even if the conjecture itself would be proved using natural proofs).

> **Comments:**
> **username_2**: Also worth pointing out that $NEXP \not\subseteq ACC^0$ uses lots of circuit results within the proof, so those circuit results certainly weren't useless! It's just the proof *also* uses diagonalization, which is how it gets around being Razborov-Rudich natural.  

---

