[FOM] P =? NP: A practically important breakthrough (Kreinovich, Vladik)

[Colin McLarty]

On Fri, Jan 15, 2016 at 9:50 PM, Arnold Neumaier <
arnold.neumaier at univie.ac.at> wrote:

>
> But P=NP might imply only that you can solve size n instances of SAT in,
> say, n^(1 million) operations. This is polynomial but has no use at all.
> Thus even when P=NP would have been proved, it might be a lot of work to
> find out which problems become tractable in a real life sense...
>
> Indeed the last I heard, this is exactly the case for the
Agrawal–Kayal–Saxena polynomial time primality test.  A beautiful
achievement, still it is much less usable for practical cases than earlier
NP tests.  Or has that changed with further progress?

Colin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160116/513470c5/attachment.html>