Re:P might be NP: A Polynomial Time Algorithm for the Hamilt...
by usamec on Wednesday May 29, 2013 @10:57AM
(#5786600)
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.
Re:P might be NP: A Polynomial Time Algorithm for the Hamilt...
by raverbashing on Wednesday May 29, 2013 @11:09AM
(#5786678)
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.
I believe there's good money to be made if you find out that P=NP
If you can solve an NP problem in polynomial time you can solve 3-SAT, and if you can solve that you can factor big numbers (even though factorization is 'easier' than NP)
Maybe you can easily reverse hash functions as well with that knowledge.