1
$\begingroup$

So I am a bit confused about the reduction between SAT, subgraph isomorphism (SI) and graph isomorphism (GI). I know that GI is in NP, and that SI is NP-complete. So I'm thinking if we can decide instances of SAT in polynomial time, then we can also solve GI and SI in polynomial time since SAT is NP-complete and if one NP-complete problem is solved, then all others are also solved.

Am I correct? Thank you!

$\endgroup$
1
$\begingroup$

Here is a more general theorem:

Let $X$ be some NP-complete problem. Then $X$ can be solved in polynomial time iff all problems in NP can be solved in polynomial time.

Indeed, if all problems in NP can be solved in polynomial time, then since $X$ is in NP, then $X$ can be solved in polynomial time.

In the other direction, suppose that $X$ can be solved in polynomial time. Let $Y$ be any problem in NP. Since $X$ is NP-hard, there is a polytime reduction $f$ from $Y$ to $X$. Using this reduction, we can reduce $Y$ to $X$, and so solve $Y$ in polynomial time. (I'm only sketching this part, since this is a standard argument which I assume you were shown in class.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ When you are talking about NP-hard, are you explaining the theorem in an extended way? To my understanding, SAT and SI are NP-complete. So why is NP-hard involved here? $\endgroup$ – MayRain Apr 29 at 9:02
  • 1
    $\begingroup$ A language is NP-complete, by definition, if it is both NP-hard and in NP. $\endgroup$ – Yuval Filmus Apr 29 at 9:03
  • $\begingroup$ thank you very much! $\endgroup$ – MayRain May 1 at 1:59

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.