Max/min CSP/Ones classification theorems

In computational complexity theory, a branch of computer science, the Max/min CSP/Ones classification theorems state necessary and sufficient conditions that determine the complexity classes of problems about satisfying a subset S of boolean relations.^[1] They are similar to Schaefer's dichotomy theorem, which classifies the complexity of satisfying finite sets of relations; however, the Max/min CSP/Ones classification theorems give information about the complexity of approximating an optimal solution to a problem defined by S.

Given a set S of clauses, the Max constraint satisfaction problem (CSP) is to find the maximum number of satisfiable (possibly weighted) clauses in S. Similarly, the Min CSP problem is to minimize this number of clauses. The Max Ones problem is to maximize the number of boolean variables in S that are set to 1 when all clauses are satisfied, and the Min Ones problem is to minimize this number.^[2]

When using the classifications below, the problem's complexity class is determined by the topmost classification that it satisfies.

Definitions

We define for brevity some terms here, which are used in the classifications below.

• PO stands for Polynomial time optimizable; problems for which finding the optimum can be done in polynomial time, so that approximation to arbitrary precision can also clearly be done in polynomial time.
• Conjunctive normal form is abbreviated CNF below.
• X(N)OR-SAT stands for a satisfiability problem which is the AND of several boolean linear equations that can be written as XOR clauses. Exactly one literal in each XOR clause must be negated (e.g. $x_1 \oplus \lnot x_2 \oplus x_3 = 1$). See XOR-SAT.
• Max UnCut-complete refers to a complexity class historically defined in terms of a problem named Max UnCut. Such problems are APX-hard but with an $O(\sqrt{\log n})$ factor approximation.^[3]
• Min 2CNF-Deletion-complete is another complexity class historically defined via a problem. Such problems are APX-hard but with an $O(\sqrt{\log n})$ approximation.^[3]
• Nearest Codeword-complete is yet another such complexity class. Such problems are inapproximable to within a $2^{\log^{1-\epsilon}(n)}$ factor for some $\epsilon$.
• Min Horn-Deletion-complete is yet another such complexity class. Such problems are inapproximable to within a $2^{\log^{1-\epsilon}(n)}$ factor for some $\epsilon$, but are in Poly-APX, so they have some polynomial factor approximation.

Classification theorems

Max CSP

The following conditions comprise the classification theorem for Max CSP problems. ^[1]

1. If setting all variables true or all variables false satisfies all clauses, it is in PO.
2. If all clauses, when converted to disjunctive normal form, have two terms, one consisting of all positive (unnegated) variables and the other all negated variables, it is in PO.
3. Otherwise, the problem is APX-complete.

Max Ones

The following conditions comprise the classification theorem for Max Ones problems. ^[1]

1. If setting all variables true satisfies all clauses, it is in PO.
2. If each clause can be written as the CNF of Dual-Horn subclauses, it is in PO.
3. If it is an instance of 2-X(N)OR-SAT, which is X(N)OR-SAT with two variables per linear equation, it is in PO.
4. If it is an instance of X(N)OR-SAT but not 2-X(N)OR-SAT, it is APX-complete.
5. If each clause can be written as the CNF of Horn subclauses, it is Poly-APX-complete.
6. If it is an instance of 2-CNF-SAT, it is Poly-APX-complete.
7. If setting all or all but one variable false satisfies each clause, it is Poly-APX-complete.
8. It is NP-hard to distinguish between an answer of 0 and a nonzero answer if setting all variables false satisfies all clauses.
9. Otherwise, it is NP-hard to find even a feasible solution.

Min CSP

The following conditions comprise the classification theorem for Min CSP problems. ^[1]

1. If setting all variables false or all variables true satisfies all clauses, it is in PO.
2. If all clauses, when converted to disjunctive normal form, have two terms, one consisting of all positive (unnegated) variables and the other all negated variables, it is in PO.
3. If all clauses are the OR of O(1) variables, it is APX-complete.
4. If it is an instance of 2-X(N)OR-SAT, it is Min UnCut-complete.
5. If it is an instance of X(N)OR-SAT but not 2-X(N)OR-SAT, it is Nearest Codeword-complete.
6. If it is an instance of 2-CNF-SAT, it is Min 2CNF-Deletion-complete.
7. If all clauses are Horn or Dual-Horn, it is Min Horn Deletion-complete.
8. Otherwise, distinguishing between an answer of 0 and a nonzero answer is NP-complete.

Min Ones

The following conditions comprise the classification theorem for Min Ones problems. ^[1]

1. If setting all variables false satisfies all clauses, it is in PO.
2. If each clause can be written as a CNF of Horn subclauses, it is in PO.
3. If it is an instance of 2-X(N)OR-SAT, it is in PO.
4. If it is an instance of 2-CNF-SAT, it is APX-complete.
5. If all clauses are the OR of O(1) variables, it is APX-complete.
6. If it is an instance of X(N)OR-SAT but not 2-X(N)OR-SAT, it is Nearest Codeword-complete.
7. If each clause can be written as a CNF of Dual-Horn subclauses, it is Min Horn Deletion-complete.
8. If setting all variables true satisfies all clauses, it is Poly-APX-complete.
9. Otherwise, it is NP-Hard to even find a feasible solution.

See also

• Boolean satisfiability problem
• APX
• MaxSNP

References

1. Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David (Mar 2000). "The Approximability of Constraint Satisfaction Problems" (PDF). Siam J. Computing (SIAM) 30 (6): 1863–1920.
2. Demaine, Erik (Fall 2014). "Algorithmic Lower Bounds: Fun with Hardness Proofs Lecture 11 Notes" (PDF).
3. Agarwal, Amit; Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury (2005). $O(\sqrt{\log n})$. Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05. New York, NY, USA: ACM. pp. 573––581.