|
|
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
|
|
