(NOTES COPY) Relativization Barrier to P vs. NP

Key Takeaway: a powerful technique, diagonalization, is doomed to fail at resolving P vs. NP.

Context

Complexity theory is generally the study of impossibilities. This is also an impossibility result. Here are some impossibility results!

The reals are uncountable [Cantor 1874]
Godel’s incompleteness theorem [Godel 1931]
halting problem is undecidable [Turing 1936]
time hierarchy theorem [Hartmanis-Stearns 1965] — $\text{P}$ is a strict subset of $\text{EXP}$

Notice! All of these theorems uses a single technique—diagonalization.

diagonalization

tl;dr: “simulate, and then, at the last minute, flip! and do the opposite.” Notice that all diagonalization problems are simulation results—you have a Turing Machine for the thing and you watch it do something / you modify it and give an algorithm.

simulation result

A hallmark of simulation results is that they continue to hold if both machines get access to the same oracle. All simulation results relativizes.

relativization

When a result continue to hold when both sides get access to the same oracle, we call these proves that “relativize”. Everything is a simulation result relatives (just re-simulate with oracles).

Here we go!

Strangely enough, these are both true facts:

\begin{equation} \exists \text{A}, \text{P}^{A} = \text{NP}^{A} \end{equation}

\begin{equation} \exists \text{B}, \text{P}^{B} \neq \text{NP}^{B} \end{equation}

The philosophical takeaway is that, regardless of what your proof of $\text{P} =^{?} \text{NP}$ relationship is, your proof better break when an arbitrary oracle is added. That is, its proof has to be “sensitive” to additional oracles. That is, it’s proof better not relativize. That is, they better not be diagonalization.

(fun fact/drama: $\exists \text{B}, \text{P}^{B} \neq \text{NP}^{B}$ is true for random oracle $B$, which gives us evidence that $\text{P} \neq \text{NP}$).

Review: Oracle Turing Machine

An oracle TM is a TM $M$ with an extra “oracle tape” that it can read-write to. $M$ has extra unit-time operation “ORACLE”.

If $z \in \qty {0,1}^{*}$, denotes the contents of the oracle tape, the entire string is erased and replaced with $1$ or $0$.

For language $A \in \qty {0,1}^{*}$, $A$-oracle TM is an oracle Turing machine where its oracle queries are answered according to whether $z \in A$.

Equality under A

Let’s first tackle:

\begin{equation} \exists A, \text{P}^{A} = \text{NP}^{A} \end{equation}

Sketch: we want to design an $\text{A}$ a lot more useful for $\text{P}$ than to $\text{NP}$

Answer: $A$ is any P-SPACE complete language.

strategy

$P \subseteq NP \subseteq PSPACE$ — polynomial hierarchy
Show: (i) $\text{NP}^{A} \subseteq \text{PSPACE}$, (ii) $\text{PSPACE} \subseteq \text{P}^{A}$
Then notice: $\text{P} \subseteq \text{NP}$ relativizes (TODO show this)

Finally, double containment!

i

Let $\text{L} \in \text{NP}^{A}$, we desire that $\text{L} \in \text{PSPACE}$

Let $\text{L} \in \text{NP}^{A}$. So $\exists$ an NTM $N$ that decides $L$.

On input $x$, you as a PSPACE machine simulate all possible computation branches up to $\text{N}\qty(x)$ Whenever it queries $A$, since $A$ is in PSACE, you as a PSPACE machine can also do it.

Equivalently, $\text{NP} \subseteq \text{PSPACE}$ relativizes, and $\text{PSPACE}^{A} = \text{PSPACE}$ if $A \in \text{PSPACE}$

ii

Let $\text{L} \in \text{PSPACE}$, we desire that $\text{L} \in P^{\text{A}}$

Recall that $A$ is PSPACE-complete. So then by definition we can just pipe $L$ through the poly-time reduction to the $A$ problem using $\text{P}^{A}$, and then call the oracle once.

Inequality under B

Let’s now find:

\begin{equation} \exists B, \text{P}^{B} \neq \text{NP}^{B} \end{equation}

Seperating Language

The separating language $L_{B} \in NP^{B} \backslash P^{B}$ (i.e. which shows the oracle $B$ causes inequality)

\begin{equation} \text{L}_{B} = \qty {1^{n} : B\text{ contains } \geq 1 \text{ length n strings }} \end{equation}

that is:

\begin{equation} \text{B} = \bigcup_{n=0}^{\infty} B_{n} \end{equation}

where

\begin{equation} B_{n} = \qty {y \in B : |y| = n} \end{equation}

That is, $1^{n} \in L_{B} \Leftrightarrow B_{n} \neq \emptyset$

The Oracle

Our $B$ will be such that $|B_{n}| \in \qty { 0, 1}$, for all $n$. That is, for a given distinct length, we either have one string of that length or no strings of that length in $B$.

Part 1

First, we want to show that no matter choice of $B$, $L_{B} \in NP^{B}$.

$\forall B, L_{B} \in NP^{B}$, in particular $\exists$ B oracle TM $M^{B}$ such that $x \in L_{B} \Leftrightarrow \exists y, M\qty(x,y)$ accepts.

Given $1^{n}$, we want to determine if $1^{n} \in L_{B}$ using an $NP^{B}$ machine. $1^{N} \in L_{B}$ if and only if we can find $\qty {y \in B : |y| = n} \neq \emptyset$.

So our oracle can just be $y \in B_{n}$.

All that’s left is to show that $L_{B} \not \in P^{B}$.

Part 2

We now want to show that $L_{B} \not \in P^{B}$

Let $M_1, M_{2} \ldots$ be the enumeration of all polytime oracle Turing machines.

Initially, $B = \emptyset$.

Construct $B$ in stages $i = 1, 2, \ldots$ where $i$ stage ensures that $M_{i}$ does not decide $L_{B}$. At stage $i \in \mathbb{N}$, there exists $n$ that is large enough 1) $2^{n} > \text{poly}\qty(n)$, so that we have space to “sneak a string”, see below and 2) also such that no length $n$ string has been included in $B$ yet. That is, we desire, $B_{n} = \emptyset$ for now.

Now let’s run $M_{i}$ on $1^{n}$, at some point it makes it first query $y_{1} \in^{?} \qty {0,1}^{*}$ to $B$ oracle. This is where we commit that $y_{1} \not \in B$. After $y_1, …, y_{j}$ (poly many, since $P^{B}$ can only make poly oracle calls), our machine will say a judgment about $B$.

Suppose $M_{i}\qty(1^{n})$ accepts; then it thinks $B_{n} \neq \emptyset$. We will actually keep $B_{n} = \emptyset$ (notice our oracle didn’t lie).

Suppose $M_{i}\qty(1^{n})$ rejects; then we can just add a string to make $B_{n} = 1$ that our $P^{B}$ haven’t asked yet. Here we need $n$ is large enough ($2^{n} > \text{poly}\qty(n)$).

Since our machine made $\leq \text{poly}\qty(n)$ many queries, and $|\qty {0,1}^{n}| = 2^{n}$, we can add a string to make $B_{n} = 1$ if we want to and we won’t run out.

(TODO this requires a bunch of faff to be formal, such as keep around the largest next value).

Fun: other barriers

algebrization barrier
natural proof barrier