2
$\begingroup$

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$

$\endgroup$
2
  • 6
    $\begingroup$ 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. $\endgroup$ Jan 17, 2023 at 8:16
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 18, 2023 at 23:15

1 Answer 1

5
$\begingroup$

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.

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 that $\mathbf{NEXP} \not\subseteq \mathbf{ACC^0}$) are non-natural.

  • The KRW conjecture, if proved, would yield lower bounds via a non-natural proof (even if the conjecture itself would be proved using natural proofs).

$\endgroup$
1
  • 4
    $\begingroup$ 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. $\endgroup$ Jan 18, 2023 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.