[FOM] Amusing observation about independence of complexity results

[Timothy Y. Chow]

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