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

[Alasdair Urquhart]

Timothy Chow's posting seems to have some kinship with work of Shai 
Ben-David and Shai Halevi.  Their paper "On the Independence of P versus
NP" (a technical report of 1991 from the Technion, available on
Ben-David's web site) discusses the question of independence of
complexity conjectures in terms of fast-growing functions.
Their main result is that if you can prove independence of
"P = NP" using standard techniques involving rate of growth of
functions, then there is a "very close to polynomial" deterministic
algorithm for SAT.  Since at the moment, we don't know of any
other non-Goedelian techniques for proving independence from PA, this 
appears to me to show that the independence route is not
currently a fruitful line to follow.

Scott Aaronson has a nice survey on the question of logical independence
of "P=NP" (Bulletin of the EATCS, 81, October 2003, also available on
his web site).

Alasdair Urquhart