Max/min CSP/Ones classification theorems

Last updated November 27, 2020

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 (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.^[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.
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({\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]

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.^[1]

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.^[1]

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.^[1]

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

Related Research Articles

In logic and computer science, the Boolean satisfiability problem is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called satisfiable. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is unsatisfiable. For example, the formula "a AND NOT b" is satisfiable because one can find the values a = TRUE and b = FALSE, which make = TRUE. In contrast, "a AND NOT a" is unsatisfiable.

In computational complexity theory, the complexity class #P is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are ♯P-complete.

In Boolean logic, a formula is in conjunctive normal form (CNF) or clausal normal form if it is a conjunction of one or more clauses, where a clause is a disjunction of literals; otherwise put, it is a product of sums or an AND of ORs. As a canonical normal form, it is useful in automated theorem proving and circuit theory.

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of intense research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint Programming (CP) is the field of research that specifically focuses on tackling with this kind of problems. Additionally, boolean satisfiability problem (SAT), the satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

In computer science, 2-satisfiability, 2-SAT or just 2SAT is a computational problem of assigning values to variables, each of which has two possible values, in order to satisfy a system of constraints on pairs of variables. It is a special case of the general Boolean satisfiability problem, which can involve constraints on more than two variables, and of constraint satisfaction problems, which can allow more than two choices for the value of each variable. But in contrast to those more general problems, which are NP-complete, 2-satisfiability can be solved in polynomial time.

In computational complexity theory, the class APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer.

MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as:

In computational complexity theory, (SAT, ε-UNSAT) is a language that is used in the proof of the PCP theorem, which relates the language NP to probabilistically checkable proof systems.

In computational complexity theory, the maximum satisfiability problem (MAX-SAT) is the problem of determining the maximum number of clauses, of a given Boolean formula in conjunctive normal form, that can be made true by an assignment of truth values to the variables of the formula. It is a generalization of the Boolean satisfiability problem, which asks whether there exists a truth assignment that makes all clauses true.

In computational complexity theory, a branch of computer science, Schaefer's dichotomy theorem states necessary and sufficient conditions under which a finite set S of relations over the Boolean domain yields polynomial-time or NP-complete problems when the relations of S are used to constrain some of the propositional variables. It is called a dichotomy theorem because the complexity of the problem defined by S is either in P or NP-complete as opposed to one of the classes of intermediate complexity that is known to exist by Ladner's theorem.

In computational complexity theory, a gadget is a subset of a problem instance that simulates the behavior of one of the fundamental units of a different computational problem. Gadgets are typically used to construct reductions from one computational problem to another, as part of proofs of NP-completeness or other types of computational hardness. The component design technique is a method for constructing reductions by using gadgets.

In computational complexity theory, SNP is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties. It forms the basis for the definition of the class MaxSNP of optimization problems.

The #P-completeness of 01-permanent, sometimes known as Valiant's theorem, is a mathematical proof about the permanent of matrices, considered a seminal result in computational complexity theory. In a 1979 scholarly paper, Leslie Valiant proved that the computational problem of computing the permanent of a matrix is #P-hard, even if the matrix is restricted to have entries that are all 0 or 1. In this restricted case, computing the permanent is even #P-complete, because it corresponds to the #P problem of counting the number of permutation matrices one can get by changing ones into zeroes.

In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence.

MAXEkSAT is a problem in computational complexity theory that is a maximization version of the Boolean satisfiability problem 3SAT. In MAXEkSAT, each clause has exactly k literals, each with distinct variables, and is in conjunctive normal form. These are called k-CNF formulas. The problem is to determine the maximum number of clauses that can be satisfied by a truth assignment to the variables in the clauses.

In computer science, the Sharp Satisfiability Problem is the problem of counting the number of interpretations that satisfies a given Boolean formula, introduced by Valiant in 1979. In other words, it asks in how many ways the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. For example, the formula $is satisfiable by three distinct boolean value assignments of the variables, namely, for any of the assignments, ,, we have = TRUE.$

In theoretical computer science, the term isolation lemma refers to randomized algorithms that reduce the number of solutions to a problem to one, should a solution exist. This is achieved by constructing random constraints such that, with non-negligible probability, exactly one solution satisfies these additional constraints if the solution space is not empty. Isolation lemmas have important applications in computer science, such as the Valiant–Vazirani theorem and Toda's theorem in computational complexity theory.

In computer science, conflict-driven clause learning (CDCL) is an algorithm for solving the Boolean satisfiability problem (SAT). Given a Boolean formula, the SAT problem asks for an assignment of variables so that the entire formula evaluates to true. The internal workings of CDCL SAT solvers were inspired by DPLL solvers.

In computability theory and computational complexity theory, especially the study of approximation algorithms, an approximation-preserving reduction is an algorithm for transforming one optimization problem into another problem, such that the distance of solutions from optimal is preserved to some degree. Approximation-preserving reductions are a subset of more general reductions in complexity theory; the difference is that approximation-preserving reductions usually make statements on approximation problems or optimization problems, as opposed to decision problems.

Given a Boolean expression $with variables, finding an assignment of the variables such that is true is called the Boolean satisfiability problem, frequently abbreviated SAT, and is seen as the canonical NP-complete problem.$

References

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

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[kstw-1] 1 2 3 4 5 Khanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David (Mar 2000). "The Approximability of Constraint Satisfaction Problems" (PDF). SIAM J. Comput. SIAM. 30 (6): 1863–1920. doi:10.1137/S0097539799349948.

[2] Demaine, Erik (Fall 2014). "Algorithmic Lower Bounds: Fun with Hardness Proofs Lecture 11 Notes" (PDF).

[acmm-3] 1 2 Agarwal, Amit; Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury (2005). " $O({\sqrt {\log n}})$ approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems". Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing. STOC '05. New York, NY, USA: ACM. pp. 573–581.

[1]

[2]

[3]