Suggest edit — (NOTES COPY) Relativization Barrier to P vs. NP

Title

Name

Note

---
title: "(NOTES COPY) Relativization Barrier to P vs. NP"
type: concept
related: [Polynomial Hierarchy]
source: https://www.jemoka.com/posts/kbhrelativization_barrier_to_p_vs_np/
confidence: high
status: active
---

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&rsquo;s incompleteness theorem [Godel 1931] halting problem is undecidable [Turing 1936] time hierarchy theorem [Hartmanis-Stearns 1965] &mdash; $\text{P}$ is a strict subset of $\text{EXP}$ Notice! All of these theorems uses a single technique&mdash;diagonalization.
diagonalization tl;dr: &ldquo;simulate, and then, at the last minute, flip! and do the opposite.&rdquo; Notice that all diagonalization problems are simulation results&mdash;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 &ldquo;relativize&rdquo;. 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 &ldquo;sensitive&rdquo; to additional oracles. That is, it&rsquo;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 &ldquo;oracle tape&rdquo; that it can read-write to. $M$ has extra unit-time operation &ldquo;ORACLE&rdquo;.
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&rsquo;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$ &mdash; 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&rsquo;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&rsquo;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} &gt; \text{poly}\qty(n)$, so that we have space to &ldquo;sneak a string&rdquo;, 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&rsquo;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, &hellip;, 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&rsquo;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&rsquo;t asked yet. Here we need $n$ is large enough ($2^{n} &gt; \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&rsquo;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