Solving subgraph isomorphism in polynomial time 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!
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.)