Scope of natural proofs barrier

Question

The natural proofs barrier of Razborov and Rudich states that under credible cryptographic assumptions one cannot hope to separate NP from P/poly by finding combinatorial properties of functions that are constructive, large, and useful. There are several well-known results that manage to evade the barrier. There are also several papers discussing possible loopholes to the three conditions, such as a result of Chow showing the barrier is sensitive to weak violations of largeness, and a recent paper of Chapman and Williams suggesting how to potentially avoid the barrier by relaxing the usefulness condition. My question is whether there are any examples, or even the possibility, of avoiding the natural proofs barrier not by violating constructiveness, largeness, or usefulness, but by falling entirely outside its scope. That is, it is not at all obvious to me why every potential method of proof should need to be based on finding combinatorial "properties" and then partitioning all functions into those that do and don't meet the property. Why must this framework of operation apply to all possible proofs, and if it doesn't then what would other types of proofs look like?

Answer 1

Let $f: \{0,1\}^* \rightarrow \{0,1\}$ be a function, and let $C$ be a class of algorithms working on finite slices of $f$. Every circuit lower bound whatsoever is a proof that $f \notin C$, for some $f$ and some $C$. Consider the "combinatorial property of Boolean functions" ${\cal P}_f$, such that

${\cal P}_f(f) = 1$ and ${\cal P}_f(g) = 0$ for all $g \neq f$.

A proof that $f \notin C$ is a proof that ${\cal P}_f$ is useful against $C$, in the terminology of Razborov and Rudich. That is, "usefulness" is totally unavoidable -- there is no way to "fall outside its scope." If you have proved a circuit lower bound at all, you have given some useful property.

Note that, if $f \in TIME[2^{O(n)}]$, then ${\cal P}_f$ is also constructive as well, in the terminology of Razborov and Rudich. So for functions $f$ computable within $E$ but not in (say) $P/poly$, constructivity would also apply to at least one property of Boolean functions that is useful against $P/poly$.

So, Razborov and Rudich is more fundamental than you might initially think.

Answer 2

You are right: the natural proofs theorem is about natural properties (and only informally about proofs). Razborov himself wrote two papers around the same time looking into the class of formal proofs and complexity lower bounds:

• Bounded Arithmetic and Lower Bounds in Boolean Complexity, 1995
• Unprovability of Lower Bounds on the Circuit Size in Certain Fragments of Bounded Arithmetic, 1995

The first studies the formalization of existing lower bound proofs in weak fragments of arithmetic (upper bounds on hardness of proving complexity theory lower bounds).

The second paper is about lower bounds on the hardness of proving stronger complexity theory lower bounds: how much math do we need to prove $\mathsf{P} \neq \mathsf{NP}$? Do we need $ZFC$? $ZF$? $PA$? Maybe at least $PV$? ($PV$ is considered the theory corresponding to reasoning using concepts in $\mathsf{P}$). An ideal result for the second paper would have been:

$PV$ cannot prove (a reasonable formalization of) $\mathsf{P} \neq \mathsf{NP}$.

To do this we would need to formalize the informal idea that we can extract natural properties from lower bound proofs in $PV$. However the results in the second paper are much weaker than this.

So it is possible to best of our knowledge that $\mathsf{P} \neq \mathsf{NP}$ has a proof that does not use any concept outside $\mathsf{P}$. In fact it is possible to best of our knowledge that much weaker theories can prove the separation.