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

Baker, Gill, and Solovay [1] showed that $\mathbf{P}$ and $\mathbf{NP}$ coincide relative to a suitable oracle. An $\mathbf{EXP}$-complete language provides one such oracle. To see this, 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}}$, fix a language $L \in \mathbf{EXP}$. There exists a deterministic Turing machine $M$ that decides $L$ in time at most $2^{p(n)}$, where $p$ is a polynomial. A deterministic Turing machine with oracle $\mathsf{EXPCOM}$ can decide $L$ using only one oracle query:

$$ x \in L \iff M(x) = 1 \iff \langle M, x, 1^{p(n)}\rangle \in \mathsf{EXPCOM}. $$

On the other hand, let $M$ be a nondeterministic polynomial-time Turing machine with an oracle $\mathsf{EXPCOM}$. One 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}}$

A stronger result will be shown:

$$ \mathbf{P}^{\mathsf{HALT}} = \mathbf{PSPACE}^{\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}} \subseteq \mathbf{PSPACE}^{\mathsf{HALT}}$, so it suffices to prove that $\mathbf{PSPACE}^{\mathsf{HALT}} \subseteq \mathbf{P}^{\mathsf{HALT}}$.

Let $L \in \mathbf{PSPACE}^{\mathsf{HALT}}$, decided by a deterministic oracle Turing machine $M$ that runs in space $S(n)$, where $S$ is a polynomial.

The Census Technique

The simulation uses a census technique employed by Allender et al. [2]: first determine how many halting instances have encodings of bounded length, then use that count to recover the relevant oracle answers.

For simplicity, pairs $\langle N, y\rangle$ are represented using a standard binary encoding that admits polynomial-time encoding and decoding. Invalid encodings are interpreted as a fixed pair whose machine never halts.

Fix an input $x$ of length $n$, and let $m = S(n)$. Since the space used by the oracle query tape is included in the space bound, 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:

  1. 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}$.
  2. Simulate $M(x)$ until it halts, answering each oracle query $q$ by checking whether $q \in H$.
  3. Halt if the simulation accepts; otherwise, loop forever.

$$\langle D_{c_m}, x\rangle \in \mathsf{HALT} \iff M^{\mathsf{HALT}}(x) \text{ accepts} \iff x \in L.$$

Since $m = S(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{PSPACE}^{\mathsf{HALT}}$, one has $L \in \mathbf{P}^{\mathsf{HALT}}$, which gives $\mathbf{PSPACE}^{\mathsf{HALT}} \subseteq \mathbf{P}^{\mathsf{HALT}}$.

Thus,

$$ \mathbf{P}^{\mathsf{HALT}} = \mathbf{NP}^{\mathsf{HALT}} = \mathbf{PSPACE}^{\mathsf{HALT}}. $$

$\mathbf{P}^A = \mathbf{NP}^A$ for $\mathbf{PSPACE}$-complete $A$

Baker, Gill, and Solovay [1] also showed that any $\mathbf{PSPACE}$-complete oracle makes $\mathbf{P}$ and $\mathbf{NP}$ coincide. 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

Baker, Gill, and Solovay [1] obtained a separating oracle by diagonalizing against deterministic polynomial-time oracle machines. To describe the construction, let $U_B$ be the unary language associated with an oracle $B$:

$$ U_B = \{1^n : \text{there exists a string of length } n \text{ in }B\}. $$

It is evident that for every oracle $B$, $U_B \in \mathbf{NP}^B$. On input $1^n$, a nondeterministic oracle Turing machine guesses a string $s \in \{0, 1\}^n$, and accepts if and only if $s \in B$, determined by an oracle query. The construction of the oracle $B$ such that $U_B \notin \mathbf{P}^B$ will be shown as follows.

The standard coding scheme is adopted here. Let $\alpha \in \{0, 1\}^*$,

$$ M_{\alpha} = \begin{cases} \text{the Turing machine described by } \alpha & \alpha \text{ is a valid encoding}, \\ M_{\text{dummy}} & \alpha \text{ is invalid}, \end{cases} $$

where $M_{\text{dummy}}$ is a machine that always rejects.

Assume that, under this encoding, every deterministic oracle Turing machine has infinitely many encodings, each of finite length.

Enumerate all finite binary strings in length-lexicographic order as $\alpha_0, \alpha_1, \ldots$, and let $M_i = M_{\alpha_i}$.

The construction of $B$ is performed in stages. In stage $i$, our construction, by determining the status of a finite number of strings (i.e., whether or not these strings will ultimately be in $B$), ensures that if the simulated machine halts within the time limit, the construction makes its answer incorrect.

In stage $i$: so far, $B$ contains a finite number of strings. Pick a length $n \geq 1$ large enough such that it exceeds the length of every string whose status has already been determined. Choosing a fresh length ensures that no string of that length has a fixed membership status. One can then keep that length empty if the simulation accepts, or add an unqueried string if it rejects.

Then, simulate the machine $M_i^B$ on input $1^n$ with a clock of $2^n - 1$ steps. Whenever it makes an oracle query, return the previously fixed answer if the queried string's membership has already been determined. Otherwise, permanently declare that string to be outside $B$.

  • If the simulation accepts, add nothing to the set $B$, and permanently declare every remaining undecided string of length $n$ to be outside $B$. Therefore, there is no string of length $n$ in $B$, which means $M_i^B$ gives an incorrect answer on input $1^n$;
  • If the simulation rejects, add an arbitrary string of length $n$ that has never been queried before. Such a string always exists because the simulation makes at most $2^n - 1$ oracle queries, whereas there are $2^n$ strings of length $n$. Hence, $M_i^B$ gives an incorrect answer on input $1^n$.
  • If the simulation does not halt within $2^n - 1$ steps, add no string to $B$ at this stage.

Fix a deterministic oracle Turing machine $M$ whose running time with oracle $B$ is bounded by a polynomial $p$. Since $M$ occurs infinitely often and the selected lengths tend to infinity, some stage assigned to $M$ uses a length $n$ satisfying $p(n) < 2^n - 1$. All oracle answers given during that stage agree with the final oracle $B$. Hence the simulation halts within the time limit and gives an incorrect answer. Thus $U_B \notin \mathbf{P}^B$.

Therefore,

$$ \mathbf{P}^B \neq \mathbf{NP}^B. $$

$\mathbf{P}^B \neq \mathbf{NP}^B$ via the Probabilistic Method

Choose $B \subseteq \{0, 1\}^*$ by including each string independently with probability $1/2$. Then

$$ \Pr_B\left[\mathbf{P}^B \neq \mathbf{NP}^B\right] = 1, $$

meaning that almost all oracles separate $\mathbf{P}$ and $\mathbf{NP}$.

To prove this separation, we adapt the construction analyzed by Hitchcock, Sekoni, and Shafei [3]. Denote by $\operatorname{bin}_n(i)$ the binary representation of $i$ of length $n$, padded with leading zeros if necessary. Define

$$ L_B = \{1^n : \exist y \in \{0, 1\}^n, \forall i \in \{0, 1, \ldots, n - 1\}, y\operatorname{bin}_n(i) \in B\}, $$

where juxtaposition denotes string concatenation.

It is evident that for every oracle $B$, $L_B \in \mathbf{NP}^B$. A nondeterministic oracle Turing machine guesses a string $y \in \{0, 1\}^n$, and makes $n$ oracle queries to determine its halting state.

For a fixed $n$, use the following table to characterize $1^n \in L_B$:

  • There are $N = 2^n$ rows in the table; each row represents a string $y$.
  • There are $n$ independently random bits in each row, where the $i$-th bit indicates whether $y\operatorname{bin}_n(i) \in B$.
  • $1^n \in L_B$ if and only if there exists a row that consists entirely of ones.

Since for each row, the probability that the row consists entirely of ones is $2^{-n} = 1/N$,

$$ \Pr\left[1^n \notin L_B\right] = \left(1 - \frac 1N\right)^N \longrightarrow e^{-1}. $$

Under this construction, both $1^n \in L_B$ and $1^n \notin L_B$ occur with constant probability.

For every deterministic Turing machine $M$ with a polynomial-time clock $p(n)$, it can be shown that for every sufficiently large $n$, the probability that its answer on input $1^n$ is incorrect is at least $1/8$, as follows.

Pick an $n$ sufficiently large, so that

$$ q \coloneqq p(n) \leq \frac N2. $$

The machine queries at most $q$ times, and so it touches at most $q$ rows. For the analysis, whenever $M$ first queries an entry in a row, reveal the entire row without changing $M$'s execution.

By the union bound,

$$ \Pr[\text{the machine touches a row that consists entirely of ones}] \leq \frac qN \leq \frac 12. $$

For a fixed complete set of query records such that none of the $k$ rows it touches consists entirely of ones, there are $N - k$ rows that have not been revealed, so

$$ \Pr\left[1^n \notin L_B \mid \text{this set of records}\right] = \left(1 - \frac 1N\right)^{N - k}. $$

Since $k \leq N/2$, one has

$$ \frac 14 \leq \left(1 - \frac 1N\right)^N \leq \left(1 - \frac 1N\right)^{N - k} \leq \left(1 - \frac 1N\right)^{N/2} \leq e^{-1/2} \leq \frac 34. $$

Therefore, conditioned on this transcript, the machine’s answer is incorrect with probability at least $1/4$, whether it accepts or rejects. Together with the fact that the probability that none of the rows $M^B(1^n)$ touches consists entirely of ones is at least $1/2$, one obtains

$$ \Pr\left[M^B(1^n) \text{ is incorrect}\right] \geq \frac 12 \cdot \frac 14 = \frac 18. \tag{$\dagger$} $$

So far, the remaining task is to change "there is a constant probability of error each time" to "with probability $1$, an error will eventually occur". Unfortunately, one cannot simply assume computations on different inputs are independent here, as they may query the same oracle rows.

Instead, choose widely separated lengths

$$ n_1 < n_2 < \cdots, \qquad 2n_{j + 1} > p(n_j), $$

and assume, without loss of generality, $p(n) \geq 2n$.

After stage $j$, reveal the membership bits of all strings of length at most $p(n_j)$. This information suffices to determine:

  • the output of $M^B(1^{n_j})$, since it cannot write down oracle queries whose length exceeds $p(n_j)$.
  • whether $1^{n_j} \in L_B$, since this depends only on oracle membership bits indexed by strings of length $2n_j$. These rows are revealed because $p(n_j) \geq 2n_j$.

Membership of $1^{n_{j + 1}}$ in $L_B$ depends only on the relevant oracle bits at length $2n_{j + 1}$, all of which remain unrevealed, so the analysis in $(\dagger)$ still holds. Therefore,

$$ \Pr\left[\bigcap_{j = 1}^r E_j\right] \leq \left(\frac 78\right)^r \longrightarrow 0, $$

where $E_j$ denotes the event that $M$'s answer on input $1^{n_j}$ is correct.

Hence, for a fixed machine $M$,

$$ \Pr_B\left[M^B \text{ decides } L_B\right] = 0. $$

There are countably many machines with a polynomial-time clock, covering all polynomial-time algorithms. The union of a countable number of zero-probability events is still a zero-probability event. Therefore,

$$ \Pr_B\left[L_B \in \mathbf{P}^B\right] = 0. $$

Together with the fact that for every oracle $B$, $L_B \in \mathbf{NP}^B$, one finally obtains

$$ \Pr_B\left[\mathbf{P}^B \neq \mathbf{NP}^B\right] = 1. $$

$\mathbf{P}^B \neq \mathbf{NP}^B$ via Time-Bounded Kolmogorov Incompressibility

Doty [4] uses time-bounded Kolmogorov complexity to construct an oracle separating deterministic and nondeterministic time. Adapting this argument, we 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$, one 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. $$

References

  1. Theodore Baker, John Gill, and Robert Solovay. Relativizations of the P = ?NP Question. SIAM Journal on Computing, 4(4), 431–442, 1975.
  2. Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger. Power from Random Strings. SIAM Journal on Computing, 35(6), 1467–1493, 2006.
  3. John M. Hitchcock, Adewale Sekoni, and Hadi Shafei. Polynomial-Time Random Oracles and Separating Complexity Classes. arXiv:1801.07317, 2018.
  4. David Doty. An Oracle Strongly Separating Deterministic Time from Nondeterministic Time, via Kolmogorov Complexity. arXiv:1004.3993, 2010.