-2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

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

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.