Relativizations of P vs NP

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
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.



One Response to Relativizations of P vs NP

  1. […] 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 […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: