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.
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.
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. ). 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 factor approximation.[3]
Min 2CNF-Deletion-complete is another complexity class historically defined via a problem. Such problems are APX-hard but with an approximation.[3]
Nearest Codeword-complete is yet another such complexity class. Such problems are inapproximable to within a factor for some .
Min Horn-Deletion-complete is yet another such complexity class. Such problems are inapproximable to within a factor for some , but are in Poly-APX, so they have some polynomial factor approximation.
Classification theoremsedit
Max CSPedit
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.
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 CSPedit
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 Onesedit
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.
^ abcdeKhanna, Sanjeev; Sudan, Madhu; Trevisan, Luca; Williamson, David (Mar 2000). "The Approximability of Constraint Satisfaction Problems" (PDF). SIAM J. Comput. 30 (6). SIAM: 1863–1920. doi:10.1137/S0097539799349948.
^Demaine, Erik (Fall 2014). "Algorithmic Lower Bounds: Fun with Hardness Proofs Lecture 11 Notes" (PDF).
^ abAgarwal, Amit; Charikar, Moses; Makarychev, Konstantin; Makarychev, Yury (2005). " 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.
April 12, 2024
ones, classification, theorems, computational, complexity, theory, branch, computer, science, state, necessary, sufficient, conditions, that, determine, complexity, classes, problems, about, satisfying, subset, boolean, relations, they, similar, schaefer, dich. 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 Contents 1 Definitions 2 Classification theorems 2 1 Max CSP 2 2 Max Ones 2 3 Min CSP 2 4 Min Ones 3 See also 4 ReferencesDefinitions editWe 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 x1 x2 x3 1 displaystyle x 1 oplus lnot x 2 oplus x 3 1 nbsp 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 nbsp 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 log n displaystyle O sqrt log n nbsp approximation 3 Nearest Codeword complete is yet another such complexity class Such problems are inapproximable to within a 2log1 ϵ n displaystyle 2 log 1 epsilon n nbsp factor for some ϵ displaystyle epsilon nbsp Min Horn Deletion complete is yet another such complexity class Such problems are inapproximable to within a 2log1 ϵ n displaystyle 2 log 1 epsilon n nbsp factor for some ϵ displaystyle epsilon nbsp but are in Poly APX so they have some polynomial factor approximation Classification theorems editMax CSP edit 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 edit 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 edit 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 edit 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 See also editBoolean satisfiability problem APX MaxSNPReferences edit a b c d e Khanna Sanjeev Sudan Madhu Trevisan Luca Williamson David Mar 2000 The Approximability of Constraint Satisfaction Problems PDF SIAM J Comput 30 6 SIAM 1863 1920 doi 10 1137 S0097539799349948 Demaine Erik Fall 2014 Algorithmic Lower Bounds Fun with Hardness Proofs Lecture 11 Notes PDF a b Agarwal Amit Charikar Moses Makarychev Konstantin Makarychev Yury 2005 O log n displaystyle O sqrt log n nbsp 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 Retrieved from https en wikipedia org w index php title Max min CSP Ones classification theorems amp oldid 1102259868, wikipedia, wiki, book, books, library,
