Diagonalization is a proof technique first used by Georg Cantor to show that some infinities are greater than others. In proof theory it is used a lot. Most famously for proving the halting problem.

Theorem(Halting problem) Not every problem is computable.

Assume to the contrary that any problem is computable. We consider \(\{(M,x) \mid M(x)\text{ halts }\}\). Then this must also be a computable, hence we can define a machine \(N\) such that \(N(M)\) does not halt if and only if \(M(M)\) halts. Now let us think if \(N(N)\) halts. We see that \(N(N)\) does not halt if and only if \(N(N)\) halts which is a contradiction.

Theorem \(\text{P}\neq \text{NP} \implies \exists B\in \text{NP}\backslash \text{P}, \neg (B\text{ is NP-complete})\)

Proof

We let \((M_e)_{e\in \mathbb{N}}\) be an enumeration of all turing machines. Assuming that \(\text{P}\neq \text{NP}\) we can take \(A\) that is not polynomial and NP-complete. Now we want to define \(B\) such that it is not polynomial and not NP-complete. We do this inductively on it’s inputs.

Let us say that we have defined \(B\) upto input \(x\). Let \(s\) be the largest number such thaat we can compute all of \(B|_s\) in \(|x|\) steps. We compute of so many \(y\) as possible if \(A(y)\neq M_e^{B|_s}(y)\) and if \(B|_s(y)\neq M_e(y)\) for all \(e

Observe that everything we do is polynomial and the assignment \(B(x)=A(x)\) is NP, hence B\(\in\)NP. Also observe that if there was a \(e\) such that \(A(y)= M_e^B(y)\) \(\forall y\) then at some point \(B(x)=0\) meaning that \(M_e^B\) is a polynomial problem, hence \(A\) is polynomial. Which is a contradiction. Therefore we know that forall \(e\) we have \(A \neq M_e^B\) proving that \(B\) is not p-T-complete and hence not p-m-complete.

Now assume there is a \(e\) such that \(B=M_e\), then at some point \(B(x)=A(x)\), again implying that \(A\) is polynomial. We conclude that \(B\neq M_e\) for all \(e\), hence \(B\) is not polynomial.

End Proof

It turns out that the p-m-degrees of NP are dense.

Oracle seperations

Theorem There exists a computable set \(A\) such that \(\text{P}^A=\text{NP}^A\).

Proof Choose \(A\) as QBF, then

\(P^A\subseteq NP^A\subseteq PSPACE^A \subseteq PSPACE \subseteq P^A\) End Proof

Theorem There exists a computable set \(A\) such that \(P^A\neq NP^A\).

Proof (Incomplete)

Let us first give a definition of \(A\). For any \(s\in \mathbb{N}\) we define A_s inductively. Let \(n\) be a number greater than we have looked thus far meaning in particular that \(A_s\cap \{0,1\}^n = \emptyset\) and we also require that \(2^n > p_s(n)\) where \(p_s\) is the amount of time machine \(M_s\) works in given input size \(n\) . If \(M_s^{A_s}(0^n)=1\), then \(A_{s+1}=A_s\). If \(M_s^{A_s}(0^n)=0\), We take \(x\in \{0,1\}^n\), such that \(A_s(x)\) is not queried my \(M_s^{A_s}\) which must exists, because \(2^n> p_s\). Now we define

\[A_{s+1}=A_s\cup \{x\}.\]

Now we define \(A := \bigcup_{s\in \mathbb{N}} A_s\) and \(B=\{0^n\mid \exists x\in \{0,1\}^n(x\in A)\}\). Observe that \(B\in \text{NP}^A\). If we show that \(B\notin P^A\) we are done. Assume to the contrary that \(B\in P\), then \(B=M_s^A\). Now let \(n\) be the number used in step \(s\), then we get that \(B(0^n)=M_s^A(0^n)\). We show that this cannot be the case. We use that \(M_s^A(0^n)=M_s^{A_s}(0^n)\) and we will check this later. Assume that \(M_s^A(0^n)=1\), we now that \(A\cap \{0,1\}^n = \emptyset\), hence \(B(0^n)=0\). Assume that \(M_s^A(0^n)\neq 0\) we know that \(x\in A\) for some \(x\in \{0,1\}^n\), hence \(B(0^n)=1\).

Finally we need to check that \(M_s^A(0^n)=M_s^{A_s}(0^n)\). By the way we chose \(x\) I see that \(M_s^{A_s}(0^n)=M_{s+1}^{A_s}(0^n)\), but I don’t way this stays true in higher stages. As tow what I can see \(x\) is only chosen considering the current machine. One solution might be to choose \(n\) large enough than input given to any oracle, but this is not specified in the lecture notes I am reading.

End Proof

\(\leq_m^p\) versus \(\leq_m^T\)

We already know that many-one reduction implies turing reduction, but we don’t know anything about the other direction. We will now prove that the other direction is not true on EXP

Theorem The relation \(\leq_m^p\) and \(\leq_T^p\) differ on EXP.

Proof

We need to come up with \(A\) and \(B\) such that \(A\leq_T^p B\), but that *(A\nleq_m^p B). Let \(f_e\) be a enumeration of all polynomial time p-m-reductions. We will define \(A_s\) and \(B_s\) inductively. First we \(n\) bigger than anything seen so far. If \(f_s(n)\in B_s\), then \(A_{s+1}=A_s\) and \(B_{s+1}=B_s\). If \(f_e(n)\notin B_s\} we choose \(A_{s+1}=\{n\}\cup A_s\) and \(B_{s+1}=\{2n,2n+1\}\cup B_s\).

First we check

End Proof