3 ms·
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
by usamec 13y 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.
- raverbashing 13y agoYes, 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.
- im3w1l 13y agoThe 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.