3
$\begingroup$

Suppose that we have a CNF SAT instance where each clause contains all variables (i.e. in each clause for each variable either the variable or its negation is presented). Such problem can be trivially solved, since any such instance either contains all possible clauses or is satisfiable.

Question: is there some a similar (i.e. with bounded number of variables that are not presented in each clause) NP-complete problem?

$\endgroup$
  • 1
    $\begingroup$ By bounded do you mean that each clause can have all but constant number of variables or, e.g. half of all variables? $\endgroup$ – rus9384 Mar 19 '18 at 13:10
2
$\begingroup$

Suppose every clause contains all but c variables. I think the problem is in $P$, which I believe can be seem from your example with $c=0$. In your case, every clause "forbids" exactly one satisfying assignment. Suppose we have $n$ variables, then the formula is satifiable when there is at least one satisfying assignment that remains, and thus, when not all $2^n$ possible assignments are forbidden.

I believe we can generalize this idea: keep a list of all such "forbidden" assignments: for each clause, add the $2^c$ assignments it forbids to the list (the opposite of the clause, with all possible extensions to the missing variables). If in the end, the list contains all $2^n$ assignments, the formula is unsatisfiable. Else, it is satisfiable

Note that this is polynomial time, if there are $m$ clauses, the list contains at most $2^c \cdot m$ forbidden 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.