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?

Improve this question
$\endgroup$
1
  • 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, 2018 at 13:10

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.