Is this problem NP-complete?

I have many restrictions like this and want to find a feasible solution:

((a and b) xor (c and d)) = 1

with a,b,c,d are arbitrary literals. It looks similar to XOR-2SAT but has additional ANDs inside the clause.

  • $\begingroup$ Are the ANDs mostly of 2 literals? ​ ​ $\endgroup$
    – user12859
    Sep 19, 2016 at 14:41
  • $\begingroup$ yes they are!!! $\endgroup$
    – guest1000
    Sep 19, 2016 at 14:47
  • 3
    $\begingroup$ Welcome to CS.SE! Can you be more precise? Do all and-clauses have exactly 2 literals? are literals always in positive form, or could they be negated? Are the xor's always of exactly 2 and-clauses? Can you edit the question accordingly? $\endgroup$
    – D.W.
    Sep 19, 2016 at 16:19

1 Answer 1


Your question is likely answered by Schaefer's dichotomy theorem. In particular, if an instance of your problem is a conjunction of formulas, each one depending on a bounded number of variables, then according to the theorem your problem is either in P or NP-complete; and moreover there is a simple criterion to decide which case it is.


Your Answer

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

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