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

[David Diamondstone]

Rather, it is less usable than earlier probabilistic algorithms (not NP
tests; formally we would say primes was already known to be in BPP), which
were already quite fast. It's not that the AKS is too slow to be usable,
just that there was no practical need for it, because for practical
purposes, being in BPP is just as good as being in P. A 2^-50 probability
that an algorithm will produce an incorrect result has no practical
drawback, since this is already vastly smaller than the chance that an
answer will be wrong due to a programming error or cosmic ray.

On Sat, Jan 16, 2016 at 11:43 AM Colin McLarty <colin.mclarty at case.edu>
wrote:

> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160120/865205ee/attachment-0001.html>