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

[martdowd at aol.com]

Arnold Neumaier writes:
 


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


 

 

 

There's an extensive literature on pracrical SAT algorithms.  Here's one link:
  http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.216.4310

Martin Dowd

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160116/33fd7fbc/attachment.html>