Re:The polynomial algorithm for 3-SAT problem (or P=NP)
by eru on Thursday January 20, 2011 @12:37PM
(#2124423)
To be pedantic, not all problems in P are equally hard. Sorting for example is harder than finding the median.
The provable lower bound for the worst-case performance of searching is O(n log n). Finding the median takes linear time i.e. O(n).
Sorting and finding a median reduce to each other polynomially, of course.
Interesting subsets of polynamial problems are e.g. linear problems, or highly parallelizeable problems whose runtime tends to O(log n) as the number of processors tends to infinity. Adding a list of numbers is not only linear but also highly parallelizeable. Proving a problem to be not parallelizeable like that, is also interesting.
There's also the question whether randomness helps. It does in practice, but we don't know whether access to random bits helps in theory.
Yes, it is. Any NP problem can be many-one reduced to SAT, which means that there's a function that transforms an instance of the NP problem to an instance of SAT, and the answer to whether that formula is satisfiable is the same as whether that instance is a member of the NP problem (in its decision version).
So who is still standing as a contender for the hardest problem in NP?
If P = NP, then all problems in NP are as easy as each other, so this question is meaningless.