[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
inputs"

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.

Tim
```