# Value of studying boolean function complexity through circuits complexity nowadays

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$$

• 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. Jan 17, 2023 at 8:16
• 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, 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. Jan 18, 2023 at 23:15

• All proofs that use diagonalization (such as Ryan Williams' celebrated proof that $$\mathbf{NEXP} \not\subseteq \mathbf{ACC^0}$$) are non-natural.
• 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. Jan 18, 2023 at 23:12