[FOM] If "NP is not in P/poly" is barely true, then it is unprovable
Alasdair Urquhart
urquhart at cs.toronto.edu
Sun Oct 5 10:57:18 EDT 2008
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
More information about the FOM
mailing list