<p>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. </p>

<p>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, <em>the time hierarchy relativizes</em>.</p>

<p>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&#39;$ relative to which $P^O = NP^O$ and $P^{O&#39;} \neq NP^{O&#39;}$, 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$. </p>

<p>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).</p>

CC BY-SA 3.0
2011-11-10T05:53:56.380Z
2011-11-10T05:53:56.380Z
Ryan Williams
<p>Are there any toy examples that provide 'essential' insights into understanding the three known barriers to $P = NP$ problem - relativization, natural proofs and algebrization?</p>

<cc.complexity-theory><relativization><p-vs-np><natural-proofs><barriers>
Toy examples for barriers to $P \ne NP$
v s
# Toy examples for barriers to $P \ne NP$

(Asked by: username_0 on 2011-11-09)

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

**Tags:** cc.complexity-theory, relativization, p-vs-np, natural-proofs, barriers


---

## 1 answers

### Answer by username_1 on 2011-11-10. Score: 27

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


---

