[FOM] Amusing observation about independence of complexity results
Timothy Y. Chow
tchow at alum.mit.edu
Thu May 22 23:33:38 EDT 2008
Here is an amusing observation regarding the idea that the existence of
contradictory relativizations of assertions such as P = 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 P = NP, then M solves SAT in polynomial time.
(Essentially M multitasks over all polytime algorithms until it jackpots.)
Suppose now that a statement such as
phi := "M correctly solves SAT in at most n^100 + 100 steps on length-n
is independent of PA (for example). The statement phi is stronger than
the statement that P = NP, but we might imagine that if P = NP is
independent of PA then something like phi will also be independent of PA.
Now phi is Pi^0_1, so if it is independent of PA then it is true, and
therefore P = NP. It follows that NP != 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 S---that is slightly stronger than PA, we can prove
"if phi is independent of PA, then NP != EXP." This in turn means that if
we can prove "phi is independent of PA" in S, then we certainly can't
prove "NP = EXP is independent of S."
Informally speaking, the upshot is that since we know that P != EXP, it is
probably too much to expect that *both* "P = NP" and "NP = EXP" are
provably independent of strong systems. On the other hand, both "P = NP"
and "NP = EXP" admit contradictory relativizations. So it seems we should
should be wary of drawing too tight a connection between contradictory
relativizations and logical independence.
More information about the FOM