World's most popular travel blog for travel bloggers.

[Solved]: NP-completeness: Reduce to or reduce from?

, , No Comments
Problem Detail: 

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

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback