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 '16 at 14:41
  • $\begingroup$ yes they are!!! $\endgroup$ – guest1000 Sep 19 '16 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 '16 at 16:19

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, privacy policy and cookie policy

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