P = NPは相対化不能
定理
$ \mathbf{P} = \mathbf{NP}は相対化不能。以下のような言語$ A, Bが存在する $ \mathbf{P}^A = \mathbf{NP}^A
$ \mathbf{P}^B \ne \mathbf{NP}^B
Proof.
$ \mathbf{P}^A = \mathbf{NP}^A
$ A := \text{EXPCOM} := \{\langle e,x,1^n \rangle \in \mathbb{B}^3\ |\ M_{e, 2^n}(x) = 1\}
$ \mathbf{P}^\text{EXPCOM} = \mathbf{NP}^\text{EXPCOM} = \mathbf{EXP}より
$ \mathbf{P}^B \ne \mathbf{NP}^B
$ U_B := \{1^n\ |\ \exists x \in B. [|x| = n] \}
と置くと$ U_B \in \textbf{NP}^B
$ 0 < c < 1となる定数をとる
任意の$ iについてある$ nが存在し$ M^B_{i, c2^{n}}(1^n) \ne U_B(1^n)となるように$ Bをとりたい
$ B_0 \coloneqq \emptyset
$ \overline{B}_0 \coloneqq \emptyset
$ B_{i+1} \coloneqq \left\{ \begin{array}{ll} B_i \cup \{x_i\} & \text{if $M^{B_i}_{i, c2^{n_i}}(1^{n_i}) = 0$} \\ B_i & \text{if $M^{B_i}_{i, c2^{n_i}}(1^{n_i}) = 1/\uparrow$} \end{array} \right.
$ \overline{B}_{i+1} := \overline{B}_i \cup \{x\ |\ \text{$M^{B_i}_{i, c2^{n_i}}(1^{n_i})$の計算で参照された$x$}\}
$ B := \bigcup_i B_i
ただし$ n_i \coloneqq \max_{x \in B_i \cup \overline{B}_i} |x| + 1
$ x_iは$ M^{B_i}_{i, c2^{n_i}}(1^{n_i})の計算において参照されない値$ |x_i| = n_iであるとする
参照される値は高々$ c2^{n_i} < 2^{n_i}なのに対し$ x_iは$ 2^{n_i}個存在するのでこのような$ x_iは存在する
任意の$ iについて
$ 1^{n_i} \in U_{B_{i+1}} \iff \exists x \in {B_{i+1}}. \left[|x| = n_i\right] \iff M^{B_i}_{i, c2^{n_i}}(1^{n_i}) = 0
より$ U_{B_{i+1}}(1^n) \ne M^{B_i}_{i, c2^n}(1^n)
$ n_j $ (j > i)は十分大きくとるため$ x_jの追加は$ iの計算を害さない
$ B_i \cap \overline{B_i} = \empty, $ B \cap \overline{B_i} = \empty
よって任意の$ iについて
$ M^B_{i, c2^{n_i}}(1^{n_i}) = M^{B_i}_{i, c2^{n_i}}(1^{n_i}) \ne U_{B_i}(1^{n_i}) = U_B(1^{n_i})
従って$ U_B \notin \textbf{DTIME}^B \left(c2^n \right)なので$ U_B \notin \mathbf{P}^B
定理
$ \mathbf{P}^G \ne \mathbf{NP}^Gとなる$ Gが存在する．
Proof.
$ U_B := \{1^n\ |\ \exists x \in B\, [|x| = n] \}
と置くと$ U_B \in \textbf{NP}^B
次を満たすように$ Gを構成する．
任意のコード$ eに対し$ n \in \Nが存在し，$ \mathfrak F_e^G(1^n) \ne U_G(1^n)
$ \mathfrak F_e^Aはコード$ eによって与えられる神託$ Aを持つ多項式時間関数 $ \mathbb P \coloneqq \sum_{n \in \omega} 2^{\{x \in \omega \mid |x| < n\}}
$ \braket{m, q} \preceq \braket{n, p} \iff m \ge n \land q \supseteq p
$ \braket{n, p} \Vdash \mathfrak F_e^G(x) = z \iff \mathfrak F^{\{z \mid p(z) = 1\}}_e(x) = z
このとき：
$ \Vdash^{\mathbb P} \forall e\, \exists m\, [\mathfrak F^G_e(1^m) \ne U_G(1^m)]
Proof.
$ \braket{n, p} \in \mathbb Pを任意に取る．
次を満たす$ w \in \omega, $ |w| \ge nを選ぶ：
クエリ$ w \in G ?は$ \braket{n, p} \Vdash \frak F_e^G(1^{|w|})の計算に使用されない．
このような$ wは存在する：$ \mathfrak F^G_e(1^k)の計算でクエリされる$ Gの引数は高々$ k^{O(1)}個なのに対し，$ |x| = kなる$ xは$ 2^k個存在するから．
$ m \coloneqq$ \braket{n,p} \Vdash \mathfrak F_e^G(1^{|w|})のクエリに現れない最小の引数のサイズ $ > |w|
$ q \colon \{x \in \omega \mid |x| < m\} \to 2を定義する：
$ q(z) \coloneqq \begin{cases} p(z) & \text{if $|z| \le n$} \\ 1 & \text{if $z = w$ and $\braket{n, p} \Vdash \mathfrak F_e(1^{|w|}) = 0$} \\ 0 & \text{o.w.} \end{cases}
このとき$ \braket{m, q} \preceq \braket{n, p}かつ$ \braket{m, q} \Vdash \frak F_e^G(1^{|w|}) \ne U_G(1^{|w|})
このとき$ \forall e\, \exists m\, [\mathfrak F_e^G(1^m) \ne U_G(1^{m})]
よって$ U_G \notin \mathbf{P}^G