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
$\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$
    – Jin
    May 30 '21 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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