patternMinor
Is SAT-Problem with XOR and AND NP-complete
Viewed 0 times
satproblemxorwithcompleteand
Problem
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.
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.
Solution
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.
Context
StackExchange Computer Science Q#63644, answer score: 4
Revisions (0)
No revisions yet.