1
$\begingroup$

enter image description here

As shown above, several NP-Complete problems are derived from GSAT (general satisfiability problem) by a polynomial-time reduction.

Then, my question is that is every pair of NP-Complete problems reduced in polynomial time? In other words, I think that the above graph should be represented as a complete graph by the definition of NP-Hard. Is it correct?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes, Let $A,B$ be two NP-complete problems. Then, by definition,

  1. $A,B\in NP$
  2. Every language $L\in NP$ can be reduced to them.

Hence, since $B\in NP$, then $B\le_p A$, and with a similar argument, $A\le_p B$.

The graph you included shows the only the reductions we used to prove NP-completeness of the problems.

$\endgroup$
1
  • $\begingroup$ Thanks for the answer! $\endgroup$
    – fitfall
    Commented May 30, 2021 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.