Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem:
Theorem- Formula F is satisfiable IFF graph has an independent set.
If I have to prove it this way does this also mean that Independent Set ≤p 3-Sat as well since the theorem goes both ways?
The statement
Formula $F$ is satisfiable $\iff$ graph has an independent set
is imprecise, since it does not specify which graph we are taling about. Correcting this, we get:
There is a polynomial-time function $\mathcal{G}$ from formulas to graphs such that, for all formulas $F$, $F$ is satisfiable $\iff$ $\mathcal{G}(F)$ has an independent set
Note that, once properly written like this, the statement is no longer symmetric: the reduction function goes in one way (formulas to graphs), and not the other way around. So, proving the above does not also prove the converse reduction.
The converse reduction (from independent set to 3-SAT) holds, but to prove that we need another reduction function $\mathcal{F}(G)$ mapping graphs into formulas.
