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:

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 \left\{0,1\right\}^{*}, denotes the contents of the oracle tape, the entire string is erased and replaced with 1 or 0. For language A \in \left\{0,1\right\}^{*}, 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:

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}\left(x\right) 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:

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

that is:

where

That is, 1^{n} \in L_{B} \Leftrightarrow B_{n} \neq \emptyset The Oracle Our B will be such that |B_{n}| \in \left\{ 0, 1\right\}, 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\left(x,y\right) 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 \left\{y \in B : |y| = n\right\} \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}\left(n\right), 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^{?} \left\{0,1\right\}^{*} 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}\left(1^{n}\right) accepts; then it thinks B_{n} \neq \emptyset. We will actually keep B_{n} = \emptyset (notice our oracle didn’t lie). Suppose M_{i}\left(1^{n}\right) 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}\left(n\right)). Since our machine made \leq \text{poly}\left(n\right) many queries, and |\left\{0,1\right\}^{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