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?


1 Answer 1


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.


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.