
Re: Naive question about P=NP and the future of mathematicians
Posted:
Feb 7, 2002 3:35 AM


"D. J. Bernstein" <djb@cr.yp.to> wrote in message news://2002Feb620.27.15.20834@cr.yp.to...
> Robin Chapman <rjc@maths.ex.ac.uk> wrote: > > And from P = NP, I doubt one could "solve" most theorems in "pure" > > mathematics. > > If P=NP then there is an algorithm with the following property: if the > input is a theorem for which there exists a proof of length n, then the > time is n^{O(1)}, and the output is a proof.
Very nice, but the question whether there is a proof of a given statement would still remain elusive.
Robin Chapman
 Posted via Mailgate.ORG Server  http://www.Mailgate.ORG

