FOM: P vs NP and Peano Arithmetic
Stephen Fenner
fenner at cse.sc.edu
Fri Aug 3 09:53:39 EDT 2001
I remember there being a theorem along these lines:
If PA + (all true Pi^0_1 sentences) does not prove P!=NP, then there is a
deterministic algorithm for SAT that runs in time n^{f(n)}, where f(n)
grows more slowly than any PA-provably recursive function.
Presumably this also holds with PA replaced with any sufficiently strong
theory. Does anybody know a reference for this result?
Steve
More information about the FOM
mailing list