I enjoy reading research on satisfiability, but sometimes it's easier to find relevant information when you know the names of the variants.


  • All the clauses are width 3 and must have exactly 1 true literals and 2 false literals: 1-in-3 SAT
  • Each clause of width n must have exactly 1 true literal and n-1 false literals: 1-in-k SAT

I'm looking for any of these, if they exist:

  • Each clause must have exactly x true literals (x not always equal to 1)

  • Each clause can have at most (or at least) x true literals

  • Each clause has a number of true literals contained in an interval

  • 1
    $\begingroup$ The last three are what is known as cardinality constraints. $\endgroup$
    – Kyle Jones
    May 13, 2020 at 1:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.