- FOM: P vs NP and Peano Arithmetic (fwd)

[Stephen Fenner]

I'm forwarding this message from a FOM nonsubscriber.  It pretty closely
addresses my question.

Steve

---------- Forwarded message ----------
Date: Sat, 4 Aug 2001 20:20:28 -0600
From: Gabriel Istrate <gistrate at yahoo.com>
To: "fenner at cse.sc.edu" <fenner at cse.sc.edu>
Subject: Re: - FOM: P vs NP and Peano Arithmetic

Dear Professor Fenner,
I am a theoretical computer scientist interested in Computational
Complexity (working at Los Alamos National Laboratory). I am a reader
of FOM in its web edition (but not a subscriber). Can you please forward
this message to the mailing-list on my behalf ?
Many thanks,
Gabriel Istrate
istrate at lanl.gov

Stephen Fenner wrote
>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

S. Ben-David and S. Halevi`` On the Independence of P versus NP'','
 Technion, TR 714, 1992.

available from http://www.cs.technion.ac.il/~shai/pub.html
All the best,
Gabriel Istrate