Question

To prove that a problem $\chi$ in NP is NP-complete, it would be sufficient to show which one of the following to be true?

• A. The problem $\chi$ can be reduced to the 3-SAT problem in polynomial time
• B. The 3-SAT problem can be reduced to $\chi$ in polynomial time
• C. The problem $\chi$ can be reduced to any other problem in NP in polynomial time
• D. Some problem in NP can be reduced to $\chi$ in polynomial time

Hint:

For NP-completeness, always reduce a known NP-complete problem to the new problem.

Answer 1

The Correct Option is B

Step 1: Definition of NP-completeness.
A problem is NP-complete if it satisfies two conditions: it is in NP, and every problem in NP can be reduced to it in polynomial time.
Step 2: Role of known NP-complete problems.
3-SAT is a well-known NP-complete problem. Reducing 3-SAT to another problem proves that the target problem is at least as hard as 3-SAT.
Step 3: Interpreting the reduction direction.
To show $\chi$ is NP-complete, a known NP-complete problem must reduce to $\chi$, not the other way around.
Step 4: Final conclusion.
Thus, showing that 3-SAT can be reduced to $\chi$ in polynomial time is sufficient to prove NP-completeness.