A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that:There exist a clause where all variables are unsatisfied.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.
Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT
satisfiability;counting
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.