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.

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

References

  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. Computing (SIAM) 30 (6): 1863–1920.
  2. Demaine, Erik (Fall 2014). "Algorithmic Lower Bounds: Fun with Hardness Proofs Lecture 11 Notes" (PDF).
  3. 1 2 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.
This article is issued from Wikipedia - version of the Wednesday, May 04, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.