Hacker News new | ask | show | jobs
by usamec 4773 days ago
P=NP doesn't imply that there is fast algorithm for every problem in NP. It only means, that there is polynomial time algorithm for everything in NP (e.g. n^100 is polynomial). For example there can be O(n^100) algorithm for solving 3-SAT, which is not fast algorithm.
1 comments

Yes, but as usually, the problem with O is the growth

In the same way that Insertion sort can be faster than Quicksort for small vectors, there's a number of elements from where even O(n^100) is quicker than O(n!)

Because the (practical) problem with NP problems is not when they are small, you can try every combination for a small TSP problem in a reasonable time.

But for big problems, even if it's n^100 instead of n! it'll be most likely faster than the existing algos.

The problem is that, even though it is faster it isn't fast enough. You can't solve any real world large problems with a n^100 algo, even though it is faster in theory.