2
$\begingroup$

A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that:

  1. There exist a clause where all variables are unsatisfied.
  2. Unfixing any variable make every clause contain at least one free variable.

Particularly for 2-SAT and 3-SAT is their number bounded by polynomial?

If yes, then how number of such assignments in SAT can be reduced from $2^m$ to polynomial, when applying Tseytin transform? $m$ is number of variables.

$\endgroup$
3
$\begingroup$

Yes, the number of minimal unsatisfiable partial assignments is upper-bounded by a polynomial.

Suppose there are $n$ clauses. There are $n$ ways to choose which clause is unsatisfied, call it $C$. Suppose clause $C$ mentions variables $x_i,x_j,x_k$. Then the partial assignment must assign values to $x_i,x_j,x_k$ but not to any other variable. (If it assigned a value to $x_\ell$, then unfixing $x_\ell$ would leave clause $C$ without a free variable, which violates the second requirement.) There is only one way to assign values to $x_i,x_j,x_k$ to make clause $C$ unsatisfied. So, there are at most $n$ minimal unsatisfiable partial assignments.

$\endgroup$

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.