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 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.

Source: Wikipedia — Max/min CSP/Ones classification theorems (CC BY-SA 4.0)