Toy examples for barriers to $P \ne NP$

Question

Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?

Answer 1

Let me give a toy example of the relativization barrier. The canonical example is the time hierarchy theorem that ${\bf TIME}[t(n)] \subsetneq {\bf TIME}[t(n)^2]$. The proof (by diagonalization) is only a little more involved than the proof that the halting problem is undecidable: we define an algorithm $A(x)$ which simulates the $x$th algorithm $A_x$ on input $x$ directly step-for-step for $t(|x|)$ steps, then outputs the opposite value. Then we argue that $A$ can be implemented to run in $t(|x|)^2$ time.

The argument works equally well if we equip all algorithms with access to an arbitrary oracle set $O$, which we assume we can ask membership queries to, in one step of computation. A step-for-step simulation of $A_x^O$ can also be carried out by $A$, as long as $A$ has access to the oracle $O$ too. In notation, we have ${\bf TIME}^O[t(n)] \subsetneq {\bf TIME}^O[t(n)^2]$ for all oracles $O$. In other words, the time hierarchy relativizes.

We can define oracles for nondeterministic machines in a natural way, so it makes sense to define classes $P^O$ and $NP^O$ with respect to oracles. But there are oracles $O$ and $O'$ relative to which $P^O = NP^O$ and $P^{O'} \neq NP^{O'}$, so this kind of direct simulation argument in the time hierarchy theorem won't work for resolving $P$ versus $NP$. Relativizing arguments are powerful in that they are widely applicable and have led to many great insights; but this same power makes them "weak" with respect to questions like $P$ versus $NP$.

The above is, of course, a toy example -- there are many other more complicated examples of arguments in complexity which still relativize (i.e., hold up when arbitrary oracles are introduced).