Very simple question, but a mistake I make often enough that I'd love to have a standard reference.
I'm showing that a problem $P$ is NP-Hard by assuming I have a polynomial time algorithm to solve $P$, then showing that this solves another NP-Hard problem $Q$ in polynomial time.
Have I reduced $P$ to $Q$ or have I reduced $Q$ to $P$?
Since $Q$ is the problem of known hardness I've chosen, have I reduced from $Q$ or reduced to $Q$?
Asked By : jmite
Answered By : Juho
To show a new problem $X$ is hard, you reduce from a problem of known hardness to $X$. For example, you can show $X$ is hard by reducing 3-SAT to $X$.
The general idea is that if you had an efficient algorithm for solving $X$, you could also solve instances of 3-SAT efficiently. This is so because you can exhibit a polynomial time transformation from a 3-SAT instance to an instance of $X$. Given an instance of 3-SAT, you transform it into an instance of $X$, apply the efficient algorithm for $X$, and thus have solved the 3-SAT instance.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/24691
0 comments:
Post a Comment
Let us know your responses and feedback