Circuit Complexity Of Constraint Satisfaction Problems With Few Subpowers

Although Constraint Satisfaction Problems (CSPs) are generally known to be NP-complete, placing restrictions on the constraint template can yield tractable subclasses. By studying the operations in the polymorphism of the constraint language, we can construct algorithms which solve our CSP in polynomial time. Previous results for CSPs with Mal’tsev [7] and generalized majority-minority operations [10] were improved to include CSPs with k-edge operations [15]. We present an alternative method to solve k-edge CSPs by utilizing Boolean trees placing the problem in the class NC2 . We do this by arranging the logical formulas describing the CSP into a Boolean tree where each leaf represents a constraint in the CSP. We take the conjunction of the constraint formulas yielding partial solutions at every step until we are left with a solution set at the root of the tree which satisfies all of the constraints.