## Separating computational classes and independence

October 7, 2008

In the spirit of a previous posting of his to the Foundations of Mathematics list that I quoted before in this blog, Timothy Chow has posted a nice observation, this time indicating how the truth of some widely believed statements about computational classes could actually lead to their unprovability in certain formal systems, via the identification of fast growing functions. I quote his message below:

[FOM] If “NP is not in P/poly” is barely true, then it is unprovable

Thursday, October 2, 2008 12:53 PM
From: Timothy Y. Chow

Here is a simple observation which is probably not new, but which I have not seen explicitly written down anywhere.  Thanks to Andreas Blass for sanity-checking the argument.

Recall that $\mathsf{P}/\mathsf{poly}$ is the non-uniform analogue of $\mathsf{P}$: It is the class of Boolean functions computable by polynomial-size Boolean circuits.  It is widely believed that

$(*)$ $\mathsf{NP}$ is not contained in $\mathsf{P}/\mathsf{poly}$.

Conjecture $(*)$ is a somewhat stronger conjecture than $\mathsf{P}\ne\mathsf{NP}$, but weaker than the conjecture that the polynomial hierarchy does not collapse.

Suppose that $(*)$ is indeed true, but only “barely true,” i.e., there exists some function $f(n)$ that is just barely superpolynomial, such that there exist Boolean circuits of size $f(n)$ that correctly solve an $\mathsf{NP}$-complete problem.  Then the promised “simple observation” is that $(*)$ is then unprovable.

To see this, fix some way of encoding $\mathsf{SAT}$ instances.  Let $n_0(d)$ be the smallest integer $n$ such that no Boolean circuit with $n$ inputs and $n^d$ gates correctly solves every instance of $\mathsf{SAT}$ (of the appropriate size). If there is no such $n$ then $n_0(d)$ is undefined.  Then $(*)$ asserts that $n_0$ is total.

The point is that if $(*)$ is barely true, then $n_0$ grows very fast.  As Andreas puts it, $f(n_0(d)) > (n_0(d))^d$ because the left side is enough gates to solve $n_0(d)$-sized instances of $\mathsf{SAT}$ while the right side isn’t. Then for $k = g(d)$ (and therefore also for $k$ not of this form with just a minor change in the estimates) $f(k) > k^{n_0^{-1}(k)}$.  Now if $f$ is just barely superpolynomial, then the exponent here, $n_0^{-1}(k)$, must be just barely above constant, and so $n_0$ grows very fast.  If it grows fast enough then your favorite formal system won’t be able to prove that it is total.

Tim

It turns out that Chow’s observation had been done before, in “On the independence of $\mathsf{P}$ versus $\mathsf{NP}$,” by Ben-David and Halevi, a technical report from 1991 available here as of this writing.

Let $\mathsf{PA}_1$ denote $\mathsf{PA}+\mathrm{Th}_{\Pi^0_1}({\mathbb N})$, $\mathsf{PA}$ augmented with all true $\Pi^0_1$ statements. In their report, Ben-David and Halevi prove:

Theorem. $\mathsf{PA}_1\vdash \mathsf{P}\ne \mathsf{NP}$ if and only if there some $\alpha<\epsilon_0$ such that the function $F_\alpha$ of the Wainer hierarchy dominates the approximation rate of $\mathsf{SAT}$ to $\mathsf{P}$.

Here, the approximation rate $R^{\mathsf{SAT}}_{\mathsf{P}}$ is defined by fixing a (canonical) enumeration of the class $\mathsf{SAT}$, say $M_1,M_2,\dots$, and setting $R^{\mathsf{SAT}}_{\mathsf{P}}(i)=\max_{j\le i}\min\{|x|:\mathsf{P}(x)\ne M_j(x)\}$. This function only depends superficially on the specific enumeration being considered, and it is a total function under the assumption that $\mathsf{SAT}$ is not in $\mathsf{P}$.

Scott Aaronson has a survey on the question of logical independence of “$\mathsf{P}=\mathsf{NP}$,” Is $\mathsf{P}$ Versus $\mathsf{NP}$ Formally Independent?, Bulletin of the EATCS 81, October 2003, as of this writing available at his website. Aaronson’s survey is not really aimed at logicians, but it is self contained and nicely written.

## Relativizations of P vs NP

June 1, 2008

In Relativizations of the ${\mathcal P}=?{\mathcal N}{\mathcal P}$ question by Theodore Baker, John Gill and Robert Solovay, SIAM J. Comput. 4 (1975), no. 4, 431-442 (available through JSTOR) it is shown that the question of whether P equals NP cannot be solved with the kind of arguments typical in computability theory, since these arguments relativize to Turing machines with oracles. Among the results shown there, two oracles $f$ and $g$ are found such that ${\sf P}^f={\sf NP}^f$ and ${\sf P}^g\ne{\sf NP}^g$. I discussed these results during 117c, the course on decidability in computability theory.

There has been some recent attempts (not very successful, and not too serious in my opinion) to show that the P vs NP question is independent of ${\sf PA}$ or even stronger systems. Apparently, part of the motivation for trying to show independence comes from the results in the Baker-Gill-Solovay paper.

I reproduce below a posting by Timothy Chow to the Foundations of Mathematics list where this motivation is shown lacking.

[FOM] Amusing observation about independence of complexity results
Thursday, May 22, 2008 8:33 PM
From:
Timothy Y. Chow

Here is an amusing observation regarding the idea that the existence of contradictory relativizations of assertions such as ${\sf P} = {\sf NP}$ is evidence that said assertions are independent of some strong theory.  I doubt this observation is new, but I haven’t seen it explicitly before.

We can write down (thanks to Levin, I think) an explicit machine $M$ with the property that, if ${\sf P} = {\sf NP}$, then $M$ solves ${\sf SAT}$ in polynomial time. (Essentially $M$ multitasks over all polytime algorithms until it jackpots.)

Suppose now that a statement such as

$\varphi:=$$M$ correctly solves ${\sf SAT}$ in at most $n^{100} + 100$ steps on length-$n$ inputs”

is independent of ${\sf PA}$ (for example).  The statement $\varphi$ is stronger than the statement that ${\sf P} = {\sf NP}$, but we might imagine that if ${\sf P} = {\sf NP}$ is independent of ${\sf PA}$ then something like $\varphi$ will also be independent of ${\sf PA}$.

Now $\varphi$ is $\Pi^0_1$, so if it is independent of ${\sf PA}$ then it is true, and therefore ${\sf P} = {\sf NP}$.  It follows that ${\sf NP}\ne{\sf EXP}$, by the time hierarchy theorem for example.

This line of reasoning can itself be formalized, and this shows that in some system call it ${\sf S}!$ that is slightly stronger than ${\sf PA}$, we can prove “if $\varphi$ is independent of ${\sf PA}$, then ${\sf NP}\ne{\sf EXP}$.” This in turn means that if we can prove “$\varphi$ is independent of ${\sf PA}$” in ${\sf S}$, then we certainly can’t prove “${\sf NP} = {\sf EXP}$ is independent of ${\sf S}$.”

Informally speaking, the upshot is that since we know that ${\sf P}\ne{\sf EXP}$, it is probably too much to expect that both${\sf P} = {\sf NP}$” and “${\sf NP} = {\sf EXP}$” are provably independent of strong systems.  On the other hand, both “${\sf P} = {\sf NP}$” and “${\sf NP} = {\sf EXP}$” admit contradictory relativizations.  So it seems we should be wary of drawing too tight a connection between contradictory relativizations and logical independence.

Tim