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


1 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).


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.