Nathann, Indeed n^99999 would do us no good. My guess is if there ever was a proof of P=NP it would include a way of constructing a polynomial time algorithm for one of the many NP-complete problems. Since most of the well known NP-complete problems have been reduced to one another, it would simply be a matter of time (rather quick time), before we had polynomial time algorithms to most NP-complete problems.
The proof in the paper seems to hinge on the fact that there cannot be a polynomial time algorithm for k-SAT, which is as hard as any NP- complete problem. On Aug 10, 9:31 am, Nathann Cohen <nathann.co...@gmail.com> wrote: > > Is it actually true that if NP-complete problems could be solved in > > deterministic polynomial time that Sage would be faster? > > No. Because knowing they are equal does not mean we can write faster > algorithms. I would be amazing if the proof of P=NP contained a way to > optimize at once all the algorithms we have found until now. And being > able to solve 3-SAT in time O( n^99999 ) would not do us any good :-) > > Nathann -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
