Given a k-SAT problem with $C$ clauses and $V$ variables, we can group the clauses together into groups of $g$ clauses with few exceptions, where the exceptions contain $g-1$ or fewer clauses. If we add the constraint that each group should contain at most $n$ variables in common, and no clause is in more than one group, how quickly can we find a "grouping" that satisfies these conditions?

I'm wondering if this problem has been considered before, and in what circumstances this problem needs to be resolved. My motivation for considering this question stems from another attempt at making use of the clause counting that I describe in this question.



Your Answer

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

Browse other questions tagged or ask your own question.