patternMinor
Satisfiability where each clause contains almost all variables
Viewed 0 times
eachallalmostsatisfiabilitywherecontainsvariablesclause
Problem
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?
Question: is there some a similar (i.e. with bounded number of variables that are not presented in each clause) NP-complete problem?
Solution
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.
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.
Context
StackExchange Computer Science Q#89413, answer score: 2
Revisions (0)
No revisions yet.