3 ms·
Up to a polynomial. What if the polynomial is of order 1000 or higher? I understand asymptotics and the convention that polynomial algorithms are "efficient".
by nandemo 16y ago
Up to a polynomial.
What if the polynomial is of order 1000 or higher?
I understand asymptotics and the convention that polynomial algorithms are "efficient". However, it might turn out that P=NP but the polynomial is so big that the found algorithm is impractical for normal sized instances.
- jacoblyles 16y agoThat's certainly a logical possibility. In practice, low-degree polynomial solutions have been developed for most important problems in P, even if the first known polynomial solution had a high degree.
- eru 16y agoWhat would be even more entertaining, is a non-constructive proof of NP=P.