[FOM] If "NP is not in P/poly" is barely true, then it is unprovable
Timothy Y. Chow
tchow at alum.mit.edu
Sun Oct 5 21:33:21 EDT 2008
> (*) NP is not contained in P/poly.
>Suppose that (*) is indeed true, but only "barely true," i.e., there
>exists some function f(n) that is just barely superpolynomial, such that
>there exist Boolean circuits of size f(n) that correctly solve an
>NP-complete problem. Then the promised "simple observation" is that
>(*) is then unprovable.
Scott Aaronson pointed out to me that this observation is made in a 1991
technical report by Ben-David and Halevi, "On the independence of P versus
NP." I had heard of this paper before but had never read it. See
or look it up on CiteSeer. For some strange and annoying reason the pages
in the electronic version of this paper appear in reverse order. Anyway,
if we let PA_1 denote PA augmented with all true Pi^0_1 statements, then
their Theorem 4 states:
PA_1 |- "P != NP" if and only if there exists F_alpha for
alpha < epsilon_0 in the Wainer hierarchy that dominates the
approximation rate of SAT to P.
Because this is an "if and only if," it provides a partial converse to the
observation I made. Roughly speaking, if you have a method for proving
independence from PA that automatically proves independence from PA_1 as
well, then your method will succeed on "P != NP" only if "P != NP" is
barely true. Or turning it around, if you think that "P != NP" is more
than barely true and you suspect it is independent of PA, then you'll have
to come up with an independence proof that doesn't generalize to PA_1.
More information about the FOM