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