News for hackers. Stuff that matters.
Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by raverbashing on Wednesday May 29, 2013 @09:47AM (#5786214)
Exactly.

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.

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.

Re:P might be NP: A Polynomial Time Algorithm for the Hamilt... by im3w1l on Wednesday May 29, 2013 @07:19PM (#5789898)
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.