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 such that parameters are accounted for in finite relation sets in a manner that satisfies algorithmic parametric requirements. 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 (in the weighted case: the maximal sum of weights) of satisfiable clauses in S. Similarly, the Min CSP problem is to minimize the number of unsatisfied clauses. The Max Ones problem is to maximize the number of boolean variables in S that are set to 1 under the restriction that all clauses are satisfied, and the Min Ones problem is to minimize this number. 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 ⊕ ¬ x 2 ⊕ x 3 = 1 {\displaystyle x_{1}\oplus \lnot x_{2}\oplus x_{3}=1} ). See XOR-SAT. Min UnCut-complete refers to a complexity class historically defined in terms of a problem named Min UnCut. Such problems are APX-hard but with an O ( log n ) {\displaystyle O({\sqrt {\log n}})} factor approximation. Min 2CNF-Deletion-complete is another complexity class historically defined via a problem. Such problems are APX-hard but with an O ( log n ) {\displaystyle O({\sqrt {\log n}})} approximation. Nearest Codeword-complete is yet another such complexity class. Such problems are inapproximable to within a 2 log 1 − ϵ ( n ) {\displaystyle 2^{\log ^{1-\epsilon }(n)}} factor for some ϵ {\displaystyle \epsilon } . Min Horn-Deletion-complete is yet another such complexity class. Such problems are inapproximable to within a 2 log 1 − ϵ ( n ) {\displaystyle 2^{\log ^{1-\epsilon }(n)}} factor for some ϵ {\displaystyle \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.
If setting all variables true or all variables false satisfies all clauses, it is in PO. 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. Otherwise, the problem is APX-complete.
Max Ones The following conditions comprise the classification theorem for Max Ones problems.
If setting all variables true satisfies all clauses, it is in PO. If each clause can be written as the CNF of Dual-Horn subclauses, it is in PO. 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. If it is an instance of X(N)OR-SAT but not 2-X(N)OR-SAT, it is APX-complete. If each clause can be written as the CNF of Horn subclauses, it is Poly-APX-complete. If it is an instance of 2-CNF-SAT, it is Poly-APX-complete. If setting all or all but one variable false satisfies each clause, it is Poly-APX-complete. It is NP-hard to distinguish between an answer of 0 and a nonzero answer if setting all variables false satisfies all clauses. Otherwise, it is NP-hard to find even a feasible solution.
Min CSP The following conditions comprise the classification theorem for Min CSP problems.
If setting all variables false or all variables true satisfies all clauses, it is in PO. 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. If all clauses are the OR of O(1) variables, it is APX-complete. If it is an instance of 2-X(N)OR-SAT, it is Min UnCut-complete. If it is an instance of X(N)OR-SAT but not 2-X(N)OR-SAT, it is Nearest Codeword-complete. If it is an instance of 2-CNF-SAT, it is Min 2CNF-Deletion-complete. If all clauses are Horn or Dual-Horn, it is Min Horn Deletion-complete. 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.
… excerpt ends here. Continue reading the full article.
