Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that:
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.
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.
