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

  1. There exists a clause where all variables are unsatisfied.
  2. Unfixing any variable makes 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 can the number of such assignments in SAT be reduced from $2^m$ to polynomial, when applying Tseytin transform? $m$ is number of variables.


1 Answer 1


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.


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.