Motivation
Humanity's research into the $\mathbf{P}$ versus $\mathbf{NP}$ problem has never ceased. Unfortunately, the deeper we investigate the problem, the more formidable it appears.
Along the way, complexity theorists have discovered three major barriers to proving strong complexity lower bounds: relativization, algebrization, and natural proofs. These barriers reveal fundamental limitations of several broad classes of proof techniques that have been successful elsewhere in complexity theory.
The failure of these approaches can certainly leave us with a sense of frustration. But there is also a more optimistic way to view these results: they effectively prune away large families of approaches that cannot possibly succeed. More importantly, these barriers reflect a deep understanding of the $\mathbf{P}$ versus $\mathbf{NP}$ problem. By identifying the limitations of existing techniques, they help us better understand what a successful proof would have to look like and which directions may be more promising.
This article will discuss the first of these barriers: relativization.
Baker-Gill-Solovay: Relativization Barrier
There exist oracles $A$ and $B$ such that $\mathbf{P}^A = \mathbf{NP}^A$ and $\mathbf{P}^B \neq \mathbf{NP}^B$.
A proof relativizes if it remains valid when all machines are given access to the same arbitrary oracle. The theorem therefore rules out any fully relativizing resolution of the $\mathbf{P}$ versus $\mathbf{NP}$ problem.
In this article, we will explore several constructions of these two kinds of oracles. Let us start with the first type.
$\mathbf{P}^{\mathsf{EXPCOM}} = \mathbf{NP}^{\mathsf{EXPCOM}}$
Let $\mathsf{EXPCOM}$ be the following language:
$$ \{\langle M, x, 1^n\rangle : \text{deterministic TM } M \text{ outputs } 1 \text{ on input } x \text{ within } 2^n \text { steps}\}. $$
It suffices to show that $\mathbf{EXP} \subseteq \mathbf{P}^{\mathsf{EXPCOM}} \subseteq \mathbf{NP}^{\mathsf{EXPCOM}} \subseteq \mathbf{EXP}$.
Trivially, one has $\mathbf{P}^{\mathsf{EXPCOM}} \subseteq \mathbf{NP}^{\mathsf{EXPCOM}}$.
To demonstrate $\mathbf{EXP} \subseteq \mathbf{P}^{\mathsf{EXPCOM}}$, the oracle $\mathsf{EXPCOM}$ allows one to compress tasks that originally required exponentially many computation steps into a single oracle query, and so $\mathbf{EXP} \subseteq \mathbf{P}^{\mathsf{EXPCOM}}$.
On the other hand, let $M$ be a nondeterministic polynomial-time Turing machine with an oracle $\mathsf{EXPCOM}$. We can simulate its execution in exponential time: this suffices both to enumerate all its nondeterministic choices and to answer its oracle queries. Therefore $\mathbf{NP}^{\mathsf{EXPCOM}} \subseteq \mathbf{EXP}$.
Finally, one gets $\mathbf{P}^{\mathsf{EXPCOM}} = \mathbf{NP}^{\mathsf{EXPCOM}} = \mathbf{EXP}$.
$\mathbf{P}^{\mathsf{HALT}} = \mathbf{NP}^{\mathsf{HALT}}$
Let $\mathsf{HALT}$ be the halting problem:
$$ \mathsf{HALT} = \{\langle M, x\rangle : M(x) \text{ halts}\}. $$
One immediately has $\mathbf{P}^{\mathsf{HALT}} \subseteq \mathbf{NP}^{\mathsf{HALT}}$, so it suffices to prove that $\mathbf{NP}^{\mathsf{HALT}} \subseteq \mathbf{P}^{\mathsf{HALT}}$.
Let $L \in \mathbf{NP}^{\mathsf{HALT}}$, witnessed by a nondeterministic oracle Turing machine $M$ that runs in time $T(n)$, where $T$ is a polynomial.
The Census Technique
For simplicity, we use a standard binary encoding of pairs $\langle N, y\rangle$, with polynomial-time encoding and decoding procedures. Invalid encodings are interpreted as a fixed pair whose machine never halts.
Fix an input $x$ of length $n$, and let $m = T(n)$. Since $M$ runs for at most $m$ steps on each branch, every oracle query has length at most $m$.
Define
$$ H_{\leq m} = \mathsf{HALT} \cap \{0, 1\}^{\leq m}, \qquad c_m = \lvert H_{\leq m} \rvert. $$
In other words, denote by $H_{\leq m}$ the set of encodings $\langle N, y\rangle$ of length at most $m$ such that $N$ halts on input $y$, and by $c_m$ the number of such encodings.
Interestingly, $c_m$ can be computed with $m + 1$ oracle queries, as follows.
Note that
$$ 0 \leq c_m \leq 2^{m + 1} - 1, $$
so its binary representation has at most $m + 1$ bits.
Hence one can use binary search to determine $c_m$. For each threshold $k$, construct the following Turing machine $C_k$, and submit $\langle C_k, x\rangle$ as a query to $\mathsf{HALT}$.
Let $C_{k, r}$ be a deterministic Turing machine, taking $x$ as input:
For each encoding of length at most $m$, decode it as $\langle N, y\rangle$, and then simulate the execution of $N$ on input $y$ for at most $r$ steps, and count the encodings for which the simulated computation halts within this time bound. If this number is less than $k$, then $C_{k, r}$ rejects; otherwise, it accepts. Note that $C_{k, r}$ always halts.
Let $C_k$ be a deterministic Turing machine, taking $x$ as input:
Try $C_{k, r}(x)$ with $r = 1$. If it accepts, then halt; otherwise, increase $r$ by $1$ and try again.
Therefore
$$ \langle C_k, x\rangle \in \mathsf{HALT} \iff C_k(x) \text{ halts} \iff c_m \geq k. $$
Once one obtains $c_m$, one oracle query to $\mathsf{HALT}$ will suffice to determine whether $x \in L$, as follows.
Let $D_{c_m}$ be a deterministic Turing machine, taking $x$ as input:
- Run $C_{c_m}(x)$, but at the same time, record the set $H$ of encodings of pairs $\langle N, y\rangle$ for which $N(y)$ halts. When this simulation terminates $\lvert H\rvert = c_m = \lvert H_{\leq m}\rvert$, so one is guaranteed that $H = H_{\leq m}$.
- Deterministically explore all computation branches of $M(x)$ for at most $m$ steps per branch, answering each oracle query $q$ by checking whether $q \in H$.
- Halt if any branch accepts; otherwise, loop forever.
$$\langle D_{c_m}, x\rangle \in \mathsf{HALT} \iff M^{\mathsf{HALT}}(x) \text{ has an accepting path} \iff x \in L.$$
Since $m = T(n)$ is polynomial in $n$, and both $k$ and $c_m$ have at most $m + 1$ bits, all query descriptions can be constructed in polynomial time. The outer algorithm constructs these descriptions without executing the machines they encode.
Therefore, for any $L \in \mathbf{NP}^{\mathsf{HALT}}$, one has $L \in \mathbf{P}^{\mathsf{HALT}}$, which gives $\mathbf{NP}^{\mathsf{HALT}} \subseteq \mathbf{P}^{\mathsf{HALT}}$.
Thus
$$ \mathbf{P}^{\mathsf{HALT}} = \mathbf{NP}^{\mathsf{HALT}}. $$
$\mathbf{P}^A = \mathbf{NP}^A$ for $\mathbf{PSPACE}$-complete $A$
Suppose $A$ is $\mathbf{PSPACE}$-complete. Then $\mathbf{PSPACE} \subseteq \mathbf{P}^A$.
Also $\mathbf{NP}^A \subseteq \mathbf{NPSPACE}$, since every query submitted to the oracle $A$ can be answered in polynomial space without recourse to the oracle $A$.
By Savitch's theorem, $\mathbf{PSPACE} = \mathbf{NPSPACE}$, and so
$$ \mathbf{NP}^A \subseteq \mathbf{NPSPACE} = \mathbf{PSPACE} \subseteq \mathbf{P}^A. $$
Therefore
$$ \mathbf{P}^A = \mathbf{NP}^A = \mathbf{PSPACE}. $$
$\mathbf{P}^B \neq \mathbf{NP}^B$ via Adversarial Diagonalization
$\mathbf{P}^B \neq \mathbf{NP}^B$ via the Probabilistic Method
$\mathbf{P}^B \neq \mathbf{NP}^B$ via Time-Bounded Kolmogorov Incompressibility
The main idea in this strategy is to construct $B$ so that, at certain lengths, it contains exactly one string that cannot be generated quickly by a short machine. If $\mathbf{P}^B = \mathbf{NP}^B$, we could recover this string efficiently by deciding whether successive prefixes extend to a string in $B$. This would yield a short machine that generates the string quickly, contradicting its defining property.
Fix an efficient universal Turing machine $U$. Define
$$ C^t(x) = \min\{\lvert a\rvert : U(a) \text{ halts with output } x \text{ within } t \text{ steps}\}. $$
Adopt the convention that $\min\varnothing = +\infty$.
Choose widely separated lengths
$$ n_1 = 2, \quad n_{j + 1} = 2^{n_j}. $$
Let $x_j$ be the lexicographically first binary string of length $n_j$ satisfying:
$$ C^{2^{n_j}}(x_j) \geq n_j, $$
and define
$$ B = \{x_1, x_2, \ldots\}. $$
Note that $x_j$ always exists, since the number of binary strings of length at most $n_j - 1$ is merely
$$ 1 + 2 + \cdots + 2^{n_j - 1} = 2^{n_j} - 1, $$
and each machine produces at most one string. However, there are a total of $2^{n_j}$ binary strings of length $n_j$. As a result, there exists one string that cannot be generated within $2^{n_j}$ steps by any program of length less than $n_j$.
Also note that $B$ is decidable, as each choice is computable by bounded simulation.
There is exactly one oracle string at each selected length. Use the prefix-extension language
$$ R_B = \{\langle 1^n, u\rangle : \lvert u\rvert \leq n, \exist v \in \{0, 1\}^{n - \lvert u\rvert}, uv \in B\}. $$
In other words, $\langle 1^n, u\rangle \in R_B$ if and only if there exists a string of length $n$ in $B$ such that it has $u$ as a prefix.
Clearly, $R_B \in \mathbf{NP}^B$.
If $R_B \in \mathbf{P}^B$, then for sufficiently large $j$, one could construct a program of length less than $n_j$ that outputs $x_j$ within $2^{n_j}$ steps, contradicting the defining property of $C^t(x)$. However, to show this, one must eliminate access to oracle $B$, since one cannot use oracles in the definition of $C^t(x)$. Suppose $R_B \in \mathbf{P}^B$. Then one has a polynomial-time Turing machine $D^B$ that decides $R_B$. One can then use $D^B$ to recover $x_j$ for each selected length $n_j$, as follows.
For each $j$, fix $n = n_j$.
Let $u = \epsilon$. Consider the machine $S^B(1^n)$ which performs the following process $n$ times:
$$ u \gets \begin{cases} u0 & D^B(\langle 1^n, u0\rangle) = 1, \\ u1 & \text{otherwise}. \end{cases} $$
$S^B(1^n)$ takes the final $u$ as its output.
There is exactly one string of length $n_j$ in $B$ and $u$ is always a prefix of $x_j$, so one has $u = x_j$ at the end.
Next, a short machine that does not use an oracle is constructed.
Let
$$ B_{<j} = \{x_1, \ldots, x_{j - 1}\}. $$
Explicitly storing $B_{<j}$ in the machine requires merely
$$ \sum_{i < j}n_i = O(n_{j - 1}) = O(\log n) $$
bits.
Equip $S$ with a polynomial clock $T(n)$ that preserves its behavior with oracle $B$ and ensures termination within $T(n)$ steps for every oracle.
For all sufficiently large $j$, one has $T(n_j) < n_{j + 1}$. Hence the clocked machine cannot query any string of length at least $n_{j + 1}$.
On queries of length less than $n_{j + 1}$, the oracles $B$ and $B_{<j}$ differ only on $x_j$. Discuss the two cases separately:
- If $S^B(1^n)$ queries $x_j$ during the reconstruction, consider its first such query. Until that point, the two simulations receive identical oracle answers and therefore follow the same computation. Thus $S^{B_{<j}}(1^n)$ also queries $x_j$.
- If $S^B(1^n)$ never queries $x_j$ during the reconstruction, the two computations are identical and both output $x_j$.
Thus, record the list of all oracle queries of length $n$ submitted by $S^{B_{<j}}(1^n)$ as
$$ q_1, \ldots, q_m, $$
and record the output of $S^{B_{<j}}(1^n)$ as $y$.
Denote by $\mathcal L(n, S)$ the list $(q_1, \ldots, q_m, y)$. One has
$$ x_j \in \mathcal L(n, S). $$
Consequently, the following information suffices for a machine to output $x_j$:
- the binary representation of $n$ requires $O(\log n)$ bits;
- the short encoding of $B_{<j}$ requires $O(\log n)$ bits;
- the index $k$ in the list $\mathcal L(n, S)$ requires $O(\log T(n)) = O(\log n)$ bits.
The machine simulates the execution of $S^{B_{<j}}(1^n)$ to generate the list $\mathcal L(n, S)$, and then outputs the specific element according to the index $k$. This takes $n^{O(1)}$ time, due to the efficiency of the universal Turing machine $U$. Hence, for a large enough $j$, one has
$$ C^{2^{n_j}}(x_j) \leq O(\log n_j) < n_j, $$
contradicting the defining property of $x_j$. Hence
$$ R_B \notin \mathbf{P}^B. $$
Together with $R_B \in \mathbf{NP}^B$, this yields
$$ \mathbf{P}^B \neq \mathbf{NP}^B. $$
Comments