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