Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
Do Natural Proofs, 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$?
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, 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).
Razborov and Rudich's result in their natural proofs paper is quite general. It is not restricted to $\mathsf{P}$ vs. $\mathsf{NP}$.
I personally like the clarity of the explanation in Stasys Jukna's recent book "Boolean Function Complexity: Advances and Frontiers":
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 Ryan Williams's papers during the last few years there were two papers that he has mentioned:
Timothy Chow, "Almost Natural Proofs", 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}$.
Eric Allender and Michal Koucký, "Amplifying Lower Bounds by Means of Self-Reducibility", 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.
