# 3SAT to CNF-SAT reduction

I am trying to prove that 3SAT is polynome time reducable to CNF-SAT, but I don't know how to do this. A formula F is in 3SAT iff f(F) is in KNFSAT, but since 3SAT is a part of KNFSAT, every formula that is in 3SAT will automatically be in CNF-SAT. Is my conclusion correct? And how do I actually show this in a correct manner?

## 1 Answer

Yes, going from 3SAT (also called 3CNFSAT) to CNFSAT (also called just SAT) is trivial. The function $f$ you are looking for is just identity, i.e., $f: x \mapsto x$, and then you are done, because, obviously, if the boolean formula $\phi$ is satisfiable (and in conjunctive form where each clause has at most three literals), i.e., in 3SAT, then $f(\phi)=\phi$ is also satisfiable and in conjunctive form, i.e., in SAT.

Usually, people are more interested in the other direction: Given a formula $\phi$ in conjunctive form, find a formula $g(\phi)$ which is equisatisfiable to $\phi$ (and thus one obtains a suitable reduction). For this, see Boolean satisfiability problem.

• Thank you so much for a good explanation! :) I think I understand it now, and I will make sure to read the link. – user2795095 Apr 7 '14 at 22:05