0
$\begingroup$

I am trying to grasp the concept of triple sat compared to 3Sat. I understand that 3Sat has 3 literals for each for each clause. ${Triple-Sat} = \{ \phi | \phi $ has at least three satisfying assignments $\}$. Im just not exactly sure what the difference is between them.

$\endgroup$

1 Answer 1

1
$\begingroup$

I don't see a connection between the two problems.

3SAT restricts the form or the formulas. A 3SAT formula can have any number of satisfying assignments. 3SAT asks for satisfiability (does there exist a satisfying assignment?)

Triple Sat is independent of the form of the formula, and simply asks a different question (do there exist three different satisfying assignments?)

$\endgroup$

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.