Meta Results on Proofs surrounding P vs NP

A lot of meta-results about $P$ vs $NP$ have been published; some general properties of proofs and techniques that must be fulfilled, some more concrete showing that certain techniques are doomed to fail.

Contents

• Barriers
  • Relativization
  • Natural Proofs
• TODO

Barriers

Relativization

Oracle Machines

In most definitions, an oracle machine is a TM that is given access to an oracle, a mechanism that answers a specific, predefined kind of question instantaneously (in one operation/costing one unit of time). The oracle is often modeled as a separate tape onto which the TM can write queries and receive answers. The resulting classes are often written as $C^A$, where $C$ is a complexity class and $A$ is an oracle.

This leads to classes like $P^{NP}$ (the class of all problems solvable in polynomial time by a TM with access to an oracle that can solve an NP-complete problem, like $SAT$, since this extends to all problems in NP via polynomial reduction), which can be shown to include $NP$ ($NP ⊆ P^{NP}$). These concepts enable more constructions, like the polynomial hierarchy $PH$.

Basic Idea

It can then be shown that oracles $A$ and $B$ exist, such that $P^A = NP^A$ and $P^B ≠ NP^B$ hold (see Baker-Gill-Solovay-1975). In other words, $P = NP$ holds relative to oracle $A$, but fails relative to oracle $B$.

A very quick introduction to relativization would be the following question from David Harris:

Is there any general definition, for a class $C$ of languages, what is the relativized class $C^A$ for an oracle $A$?

and the answer by Timothy Chow:

The short answer is no. The simplest way to see that $C^A$ cannot possibly depend only on $C$ and $A$ as sets of strings is the following spurious argument that has confused generations of students. Assume that $P = NP$. Then for all oracles $A$, $P^A = NP^A$. But by Baker–Gill–Solovay, we know that there exists an oracle $A$ such that $P^A ≠ NP^A$. This is a contradiction. Hence $P ≠ NP$. Q.E.D., and I await my $1 million check.

Note: the flaw in this argument as noted by the author himself is the assumption that $P = NP$ implies $P^A = NP^A$. Even though the sets of languages captured in the definitions of the two complexity classes match, the definitions themselves differ, and so may also the effects of giving access to an oracle.

When working with relativizations, special care needs to be taken, as even small changes in definitions of classes (see $IP$ vs $IPP$ in Chang1994) and oracle access mechanisms (see relative.pdf) can change results.

Notation

It is said that a statement $B \sim C$ relativizes if $B^A \sim C^A$ remains true for all oracles $A$. [citation needed]

Similarly, a proof technique is said to relativize if it is unaffected by the addition of an oracle.

A positive relativization of a statement $B \sim C$ is an example of an oracle $A$ for which $B^A \sim C^A$ holds. A negative relativization of a statement $B \sim C$ is an example of an oracle $A$ for which $B^A ≁ B^A$ ( $¬(B^A \sim C^A)$ ) holds.

Relevance in Complexity Theory

Intuitively, a statement relativizes if its truth is insensitive to broadening the definition of computer, from an ordinary Turing machine to one with oracle access to an arbitrary language O.

- Bariş Aydinlioğlu, Eric Bach. Affine Relativization: Unifying the Algebrization and Relativization Barriers

Relativization can be used to determine if certain proof techniques are applicable to a problem. For example, since $P$ vs $NP$ does not relativize (in either direction), any technique solving the problem must not relativize either. This is described as the barrier of relativization that any proof for $P$ vs $NP$ has to overcome.

Great care needs to be taken when drawing conclusions from relativization-related results; a particularly problematic topic are space-bound complexity classes, as the use of the oracle tape provides room for interpretation. TODO extend

It is noted that most known proof techniques relativize (see relative.pdf). Conversely, it can also serve as a heuristic for the difficulty and solvability of a problem; if there are no known negative relativizations for a statement, a relativizing proof may yet be possible. (see relative.pdf)

An often cited result regarding relativization is that $IP = PSPACE$ holds (see Shamir1992) even though there exist contradictory relativizations $IP^A = PSPACE^A$ and $IP^B ≠ PSPACE^B$ (see Fortnow1988) and $IP ≠ PSPACE$ holds for almost all oracles (see Chang1994). (all cited in this answer)

Arithmetization and Algebrization

The technique that was used to prove $IP = PSPACE$ (Shamir1992) transforms quantified formulas over boolean values into arithmetic formulas over a field like the integers and reasons about the resulting polynomials in a process that was coined arithmetization by Babai1991.

Aaronson2009 expand this idea to include oracle access to field extensions $A'$ of boolean oracles $A$ (all polynomials over finite fields (1) that match the boolean oracle's output if the query length matches and (2) with degree bound by a constant) and name the resulting barrier algebrization.

Note that a boolean oracle in this context is a function $A: {0,1}^n → {0,1}$.

An inclusion $C ⊆ D$ algebrizes if $C^A ⊆ D^{A'}$ holds for all oracles $A$ and extensions $A'$. A separation $C \not⊂ D$ algebrizes if $C^{A'} \not⊂ D^A$ holds for all oracles $A$ and extensions $A'$.

The asymmetry in the definition seems integral for the desired property of the constructed barrier to separate previously shown results that do not relativize (like $IP = PSPACE$, which algebrizes) from those that seem harder to achieve (like $P$ vs $NP$, which is shown not to algebrize).

Local Checkability

Arora1992 formalize the notion that "checking the correctness of a computation is simpler than performing the computation itself" by introducing two similar "proof checker" complexity classes with different definitions $PF\text -CHK(t(n))$ and $WPF\text -CHK(t(n))$.

[...] if someone provides a complete transcript of a computation, its correctness is easily checkable through examining its local properties.

The Local Checkability Theorem (LCT) is introduced as $NP = PF\text -CHK(log\ n)$, and similarly, the weak LCT as $NP = WPF\text -CHK(log\ n)$. Both results are true in the "real world" but do not relativize. Further, it is shown that if an oracle $O$ exists, relative to which the LCT or weak LCT holds, such that $P^O ≠ NP^O$, then $P ≠ NP$ holds in the "real world".

The Relativizing Complexity Theory (RCT) is introduced as a set of axioms, from which all* (complexity-theoretic) relativizing statements follow. Adding the LCT results in a stronger set of axioms ("RCT + LCT"), since the LCT does not relativize. It is shown that "if any interesting facts (like $P ≠ NP$) are provable in normal mathematics, then essentially the same facts are provable with RCT + LCT".

* all complexity-theoretic statements that relativize and in which time is specified within polynomial bounds and space within constant bounds.

(some) more at https://cstheory.stackexchange.com/a/20515

Natural Proofs

Razborov1997 introduce the notion of natural proofs which define (explicitly or implicitly) and reason about useful and natural combinatorial properties which are defined as follows:

$F_n$ is the set of boolean functions with $n$ parameters ($f_n: {0,1}^n → {0,1}$). $|F_n| = 2^{2^n}$, since every $2^n$ long string of bits can be interpreted as a truth table of a boolean function with $n$ parameters. A combinatorial property $C_n$ is a subset of all boolean functions with $n$ parameters ($C_n ⊆ F_n$). A combinatorial property is natural if there exists a sub-property $C^\ast_n ⊆ C_n$ that satisfies two conditions: $C^\ast_n$ is decidable in polynomial time ("constructivity") and its size is non-negligible ("largeness"). A combinatorial property is useful against $P/poly$ if the circuit size of any family of functions ${f_1, ..., f_n, ...}$ with $f_n ∈ C_n$ is super-polynomial.

Under the assumption that pseudo random generators (PRG) with exponential hardness exist, it is shown that no useful natural proof can prove lower bounds of complexity classes. Since the useful natural combinatorial property defined in such a proof could be used to create a statistical test against a PRG, which, by definition of PRGs, is not possible, posing a contradiction.

Since proving $P ≠ NP$ would prove a lower bound for $NP$ [always?], there can be no natural proof for this statement. Proofs that employ diagonalization are inherently non-natural [Aaronson2009].

TODO

• linear programming, see work of Mihalis Yannakakis (tl;dr expressing NP problems as linear programs ~always results in exponential size)
• random-access machine with unit multiplication
  • allows encoding arbitrarily many values into one cell and processing in O(1) time and space
  • the same applies to some other operations including bitwise logical operators
• Blum axioms