Sparsification for Constraint Satisfaction Problems
Constraints satisfaction problems (CSPs) and sparsification techniques for such problems are explored in this content. The process involves reducing instances efficiently, polynomial-time sparsification, and techniques like systematic sparsification for specific CSPs.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
(1, (0, (0, 0, 1, 0, 0) 0) 1) Sparsification for Constraint Satisfaction Problems ?1/3= Bart M. P. Jansen Based on joint work with Hubie Chen & Astrid Pieterse WORKER 2019 June 5th2019, Bergen, Norway
Maltsev embeddings TALK LANDSCAPE
CSPs and sparsification General class of decision problems of the form: find an assignment to ?1, ,??that satisfies all constraints Classic examples of a constraint (?,?,?): 3-CNF-SAT: at least one of ?,?,? is TRUE 3-NAE-SAT: at least one is TRUE, at least one is FALSE 1-IN-3-SAT: exactly one of ?,?,? is TRUE Complexity of the problem depends on the type of constraints Polynomial-time sparsification: efficiently reduce any ?-variable instance to ? ??constraints, for ? as small as possible 3
Warm-up: 1-IN-3 SAT Constraints are redundant when they are implied by others Consider the following instance on variables {?,?,?,?,?}: ?, ?, ? ?, ?, ? ?, ?, ? (?, ?, ?) ? + ? + ? = 1 ? + ? + 1 ? = 1 ? + 1 ? + ? = 1 ? + ? + ? = 1 + + TRUE = 1 FALSE = 0 When the first three constraints are satisfied, their equalities hold, so the fourth holds as well If each constraint ? is equivalent to an equality ?(?), and ? ? is a linear combination of the equalities of the other constraints, then ? is redundant and can be omitted General principle: Removing 4thconstraint preserves the set of sat. assignments 4
Systematic sparsification for 1-in-3 SAT Input: Instance of 1-IN-3 SAT on {?1, ,??} with ? constraints write each constraint as a linear equality ??, ??, ?? becomes ??+ 1 ?? + 1 ?? = 1 rewrite the equalities in matrix form, with 0 as right-hand sides ?1,?1 ?1,?? ??,?1 ??,?? assignment satisfies ? if and only if it satisfies ? For all ? , there is a polynomial-time algorithm that, given an instance (?,?) of 1-IN-?-SAT on ? variables, outputs a ?1 ?? 1 ?1,1 ??,1 0 0 ? rows subset ? ? of at most ? + 1 constraints such that a truth = ? + 1 columns Gaussian elimination yields basis ? of at most ? + 1 rows Output: instance on the ?(?) constraints corresponding to ? 5
Number of constraints versus encoding size For 1-IN-?-SAT we sparsified to ? + 1 constraints Asymptotically optimal: reduce to ?(?) constraints ? = ?? You can encode a constraint on ? variables in ?(?log?) bits For ? ?(1), instance can be encoded in ?(?log?) bits Yields encoding size ?(?2) for EXACT SAT There is no (generalized) kernelization for EXACT SAT (?) of bitsize ?(?2 ?) for any ? > 0, assuming ?? ????/???? [J&Pieterse@MFCS 16] We focus on CSPs with constant-arity constraints from now on Encoding size number of constraints, up to ?(log?) factor 6
Towards optimal sparsification For 1-IN-?-SAT we sparsified to ? + 1 constraints Asymptotically optimal: reduce to ?(?) constraints ? = ?? Standard ?-SAT problem can be sparsified to ? ??constraints: There are only 2??= ? ??distinct clauses possible ? 3: there is no (generalized) kernelization for ?-SAT (?) of bitsize ?(?? ?) for any ? > 0, assuming ?? ????/???? [Dell&v.Melkebeek@JACM 14] 1-IN-3-clause is satisfied number of satisfied literals is 1 3-SAT-clause is satisfied number of satisfied literals 1,2,3 3-NAE-clause is satisfied number of satisfied literals {1,2} 7
Sparsification for 3-NOT-ALL-EQUAL SAT 3-NAE-clause (?,?,?) can be written as a degree-2 equality: Variables ?,?,? {0,1} are not all equal to the same value ?? + ?? + ?? ? ? ? = 1 Setting of variables Value of left-hand side All equal to 0 0 All equal to 1 3 pairs 3 variables = 0 Single variable is 1 0 pairs 1 variable = 1 Two variables are 1 1 pair 2 variables = 1 8
Sparsification for 3-NOT-ALL-EQUAL SAT 3-NAE-clause (?,?,?) can be written as a degree-2 equality: Variables ?,?,? {0,1} are not all equal to the same value ?? + ?? + ?? ? ? ? = 1 Set of ? 3-NAE-constraints can be rewritten in matrix form: ?1 ?? ?1,?1 ??,?1 ?1,?? ?1,?1 ?2 ??,?1 ?2 ?1,?? 1 ?? ?1,1 ??,1 0 0 ?1 ?2 ?? 1 ?? 1 = ??,?? ??,?? 1 ?? ?(?2) columns Gaussian elimination yields basis ? of ?(?2) rows Output: instance on the ?(?2) constraints corresponding to ? 9
General sparsification for ?-NAE-SAT ?-NAE clause on literals 1, , ?is satisfied ?-NAE-SAT has a polynomial-time sparsification to ? ?? 1 constraints that can be encoded in ?(?? 1log?) bits number of satisfied literals lies in {1, ,? 1} ? 1 ? ? ?( ?) = 0 ?=1 ?=1 ?? if ?= ?? if ?= ?? where ?( ?) = 1 ?? So ?-NAE clauses can be written as degree-(? 1) equalities 10
Maltsev embeddings TALK LANDSCAPE
Capturing constraints by degree-1 polynomials Consider constraint-type of arity 3, with satisfying assignments: ? 1,0,0 = ?0 ? 0,1,0 = ?0 ? 0,0,1 = ?0 ? 1,1,1 = ?0 +?1 +?2 +?3 1,0,0 0,1,0 0,0,1 1,1,1 +0.5 +0.5 +0.5 0.5 = 0 = 0 = 0 = 0 ? = +?1+ ?2+ ?3 = 0 0,0,0 ? ? 0,0,0 = ?0 Is there a linear polynomial ?(?1,?2,?3) representing ?, so that ?1,?2,?3 0,13: 3 ? ?1,?2,?3 = ?0+ ?=1 ?? ??= 0 ?1,?2,?3 ? ? Not over the reals, but 1 + ?1+ ?2+ ?3 20 suffices over GF2 12
Capturing constraints by degree-1 polynomials Consider constraint-type of arity 3, with satisfying assignments: ? 1,1,0 = ?0 ? 0,1,1 = ?0 ? 1,0,1 = ?0 ? 1,1,1 = ?0 +?1+ ?2 +?2+ ?3 +?1+ ?3 +?1+ ?2+ ?3 1,1,0 0,1,1 1,0,1 1,1,1 +1 +1 +1 2 = 0 = 0 = 0 = 0 ? = = 0 0,0,0 ? ? 0,0,0 = ?0 Is there a linear polynomial ?(?1,?2,?3) representing ? , so that General obstruction principle: If unsatisfying tuple ? can be written as ?? ??for satisfying tuples ?1, ,??with ??= 1 and ?? , there is no linear polynomial ? over any ring with all ? ?? = 0 but ? ? 0 3 ? ?1,?2,?3 = ?0+ ?=1 ?? ??= 0 ?1,?2,?3 ? ? Not over any ring! 13
Climbing towards generality Mal tsev embeddings TALK LANDSCAPE
Constraint languages A constraint language is a (finite) set of (Boolean) relations ?? (1, (0, (0, 0, 1, 0, 0) 0) 1) (0, (1, (1, 0, 1, 0, 0) 0) 1) ?0= ?1= (0, (1, (1, 1, 0, 1, 0) 0) 1) (0, (1, (1, 1, 0, 1, 1) 1) 0) ?2= ?3= Clause (?,?,?) is 1-IN-3 satisfied Clause ( ?, ?,?) is 1-IN-3 satisfied ?,?,? ?2 ?,?,? ?0 Any 1-IN-3 clause can be written as ?,?,? ?? 1-IN-3-SAT is equivalent to CSP with constraints from = {?0,?1,?2,?3} 15
The CSP corresponding to a constraint language A constraint language is a (finite) set of (Boolean) relations ?? ??(??) denotes the arity of relation ?? CSP( ) Input: Set of variables ? = ?1, ,??, set of constraints ?, where a constraint ? is a pair ? , ??? ? Does an assignment ?:? {0,1} exist, such that for all ?, ?1, ,??? ? Question: ? we have: ? ??1, ,? ???? ? ?? 16
Characterizing CSP complexity based on Schaefer s dichotomy theorem For each finite Boolean constraint language , CSP is either P-time solvable or NP-complete Elegant characterization in terms of closure properties of using universal algebra Challenge from a parameterized perspective: Given , what is the best bound ?(??) on sparsification size? ?(??) constraints polynomial time (?,? ) ? ? (?,?) 17
Timeline of polynomial-time sparsification [Chen, J & Pieterse, IPEC] [Dell & van Melkebeek, STOC] Characterizations for symmetric and low-arity CSP ?-SAT cannot be sparsified to ?(?? ?) clauses [J & Pieterse, IPEC] ?-NAE-SAT can be sparsified to ? ?? 1 clauses 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 Exact SAT can be sparsified to ?(?) clauses CSP( root-of-deg-?-poly ) can be sparsified to ? ?? constraints [J & Pieterse, MFCS] CSP( ) when admits a Mal tsev embedding over finite domain: ?(?) constraints [Lagerkvist & Wahlstr hm, CP] WORKER 18
The polynomial framework for sparsification Relation ? 0,1?is captured by degree-? polynomials, if there are degree-? polynomials ??over /?? for ? [?] s.t. ?1, ,?? ? ? [?]:???1, ,?? ??0 [Boolean assignment satisfies ? iff it is a root of all ? polynomials] ? ? ? ? ? ? ? ? 1,1,0,0,1,0,0 1,0,1,0,0,1,0 (1,0,0,1,0,0,1) (0,1,1,0,0,0,1) (0,1,0,1,0,1,0) (0,0,1,1,1,0,0) (0,0,0,0,1,1,1) ? ? ? ?FANO= ? ? ? 19
The polynomial framework for sparsification Relation ? 0,1?is captured by degree-? polynomials, if there are degree-? polynomials ??over /?? for ? [?] s.t. ?1, ,?? ? ? [?]:???1, ,?? ??0 [Boolean assignment satisfies ? iff it is a root of all ? polynomials] For each of the 7 lines of the Fano plane, the variables of an odd number of points on the line are set to 1 ?,?,?,?,?,?,? 0,17: ? ?,?,?,?,?,?,? ?FANO ? + ? + ? 21, and ? + ? + ? 21, and ? + ? + ? 21, and ? + ? + ? + ? + ? + ? + ? 113 ? ? ? In total, exactly 3 variables are set to 1 ? ? ? 20
The polynomial framework for sparsification Relation ? 0,1?is captured by degree-? polynomials, if there are degree-? polynomials ??over /?? for ? [?] s.t. ?1, ,?? ? ? [?]:???1, ,?? ??0 [Boolean assignment satisfies ? iff it is a root of all ? polynomials] Relation ?FANOcannot be captured using only polynomials modulo 2 ? ? ? ? ? ? ? ? + + 1,1,0,0,1,0,0 1,0,0,1,0,0,1 (1,0,1,0,0,1,0) ? ? ? 2 1,1,1,1,1,1,1 ?FANO ? ? ? 21
The polynomial framework for sparsification Relation ? 0,1?is captured by degree-? polynomials, if there are degree-? polynomials ??over /?? for ? [?] s.t. ?1, ,?? ? ? [?]:???1, ,?? ??0 [Boolean assignment satisfies ? iff it is a root of all ? polynomials] Summary of the sparsification framework [J & Pieterse, MFCS 16] If each relation ? can be captured by degree-? polynomials, then an ?-variable instance (?,?) of CSP( ) can efficiently be reduced to an instance (?,? ?) such that: The instances have exactly the same satisfying assignments The number of constraints in ? is ?(??) [Reduction follows from Gaussian elimination; ?( ) hides factors depending on ] 22
Questions about polynomial representations If each Boolean ? can be captured by deg-? polynomials, then CSP( )has a sparsification with ?(??)constraints Powerful tool that raises several questions: Which ? can be captured using degree less than ??(?)? [Constraint languages over such ? have nontrivial sparsification; beat worst-case] Which ? can be captured by degree-1 polynomials? [Gives linear sparsification; best-case behavior] How to find such polynomials? 23
When is nontrivial sparsification possible? Let be an intractable finite Boolean constraint language, let ? be the maximum arity of a relation in For fixed , there are ?(??) possible constraints on ? variables When can we get a sparsification with ?(?? ?) constraints? If each arity-? relation ? in has 0,1? ? 1, then CSP can efficiently be sparsified to ?(?? 1) constraints [If 0,1? ? 1, then ? can be captured by a degree-(? 1) polynomial] If contains an arity-? relation ? with 0,1? ? = 1, then CSP has no efficient sparsification to ?(?? ?) constraints for any ? > 0, unless NP coNP/poly [Chen, J & Pieterse, IPEC 18] 24
Proof sketch: nontrivial sparsification If ? 0,1?with 0,1? ? > 1 and ? 0,1? ?, then there is a degree ? 1 polynomial ? ?1, ,?? over s.t. (1) ? ?1, ,?? 0 (2) ? ?1, ,?? = 0 ?1, ,?? ? Proof by induction on ?. If ? = 1, then ? = since 0,1 ? > 1. It suffices to use the following degree-0 polynomial: ? ?1, ,?? 1 since it is nonzero on ? while (2) is vacuously true 25
Proof sketch: nontrivial sparsification If ? 0,1?with 0,1? ? > 1 and ? 0,1? ?, then there is a degree ? 1 polynomial ? ?1, ,?? over s.t. (1) ? ?1, ,?? 0 (2) ? ?1, ,?? = 0 ?1, ,?? ? If ? > 1, choose ? 0,1? ? with ? ? (Case 1) If ? and ? agree on some position, assume ? = ?1, ,?? 1,1 , ? = (?1, ,?? 1,1) [no big loss of generality] Define ? { ?1, ,?? 1 ?1, ,?? 1,1 ?} of arity ? 1 Then 0,1? 1 ? > 1 as ?1, ,?? 1, ?1, ,?? 1 ? IH: exists ? (?1, ,?? 1) zero on ? but not on ? (?1, ,?? 1) Then ? ?1, ,?? ?? ? (?1, ,?? 1) suffices 26
Proof sketch: nontrivial sparsification If ? 0,1?with 0,1? ? > 1 and ? 0,1? ?, then there is a degree ? 1 polynomial ? ?1, ,?? over s.t. (1) ? ?1, ,?? 0 (2) ? ?1, ,?? = 0 ?1, ,?? ? If ? > 1, choose ? 0,1? ? with ? ? (Case 2) If ? and ? disagree on every position, assume ? = 0, ,0 , ? = (1, ,1) [no big loss of generality] ? 1? ?=1 ? Use the polynomial ? ?1, ,?? ?=1 ?? ? 1? 0 Then ? ?1, ,?? = ? 0, ,0 = ?=1 27
Proof sketch: nontrivial sparsification If ? 0,1?with 0,1? ? > 1 and ? 0,1? ?, then there is a degree ? 1 polynomial ? ?1, ,?? over s.t. (1) ? ?1, ,?? 0 (2) ? ?1, ,?? = 0 ?1, ,?? ? If ? > 1, choose ? 0,1? ? with ? ? If each arity-? relation ? in has 0,1? ? 1, then CSP can efficiently be sparsified to ?(?? 1) constraints (Case 2) If ? and ? disagree on every position, assume ? = 0, ,0 , ? = (1, ,1) [no big loss of generality] ? 1? ?=1 ? Use the polynomial ? ?1, ,?? ?=1 ?? ? For ?1, ,?? ? we have ? ( ?=1 so ? ?=1 ?? = 0 and ? ?1, ,?? = 0 ??) {1, ,? 1} ? QED 28
Open: Nontrivial sparsification for larger domains Result shows which Boolean allow nontrivial sparsification For constraint languages over larger domains, little is known Open problem: Characterize the finite constraint languages on a domain of size 3, for which CSP( ) has a nontrivial sparsification (compression to ?(?? 1) bits with ? maximum arity in ) 29
Climbing towards generality Mal tsev embeddings TALK LANDSCAPE
Our results: Capturing by linear polynomials Relation ? 0,1?is preserved by all alternating operations, if ?1, ,?2?+1 ? the following implication holds: let ? ?1 ?2+ ?3 ?4+ ?5+ + ?2?+1; if ? 0,1?then ? ? [if an alternating sum of sat. assignments yields a 0/1-assignment ?, then ? satisfies ?] (1, (0, (1, 0) 1) 1) ? 2= is not preserved 1,0 1,1 + 0,1 = 0,0 ? 2 31
Our results: Capturing by linear polynomials Relation ? 0,1?is preserved by all alternating operations, if ?1, ,?2?+1 ? the following implication holds: let ? ?1 ?2+ ?3 ?4+ ?5+ + ?2?+1; if ? 0,1?then ? ? [if an alternating sum of sat. assignments yields a 0/1-assignment ?, then ? satisfies ?] (1, (0, (0, 0, 1, 0, 0) 0) 1) ?1/3= is preserved 1,0,0 0,1,0 + 0,0,1 = +1, 1,+1 0,1? 32
Our results: Capturing by linear polynomials Relation ? 0,1?is preserved by all alternating operations, if ?1, ,?2?+1 ? the following implication holds: let ? ?1 ?2+ ?3 ?4+ ?5+ + ?2?+1; if ? 0,1?then ? ? [if an alternating sum of sat. assignments yields a 0/1-assignment ?, then ? satisfies ?] [Chen, J & Pieterse, IPEC 18] Boolean relation ? can be captured by linear polynomials ? is preserved by all alternating operations Relation preserved by all alternating operations is called balanced Constraint language consisting of balanced relations is called balanced 33
Balanced relations have linear representations Ideas in the proof: For each unsatisfying assignment ? 0,1? ?, find deg-1 poly ? with ? ? ?0 and ? ? ?0 ? ? Find ? find coefficients ? of ? solve linear system Exploit Smith decomposition, and: if ? ? ?? has no solutions for any prime power ?, it has no solutions over Boolean relation ? can be captured by linear polynomials ? is preserved by all alternating operations Relation preserved by all alternating operations is called balanced Constraint language consisting of balanced relations is called balanced 34
Balanced relations have linear representations Consequences: is balanced CSP can be sparsified to ?(?) constraints is not balanced witnessed by an alternating operation Witnesses can turn into lower-bound proofs for sparsification! Boolean relation ? can be captured by linear polynomials ? is preserved by all alternating operations Relation preserved by all alternating operations is called balanced Constraint language consisting of balanced relations is called balanced 35
Climbing towards generality Mal tsev embeddings TALK LANDSCAPE
Sparsification for symmetric CSPs A Boolean relation ? 0,1?is symmetric if ? ? depends only on the number of 1 s in ?, and not on the position of the 1 s in ? [Symmetric ? is characterized by the weights of the satisfying assignments] We say is symmetric if each ? is symmetric Let be a finite symmetric intractable Boolean constraint language Assuming NP coNP/poly, we have: CSP( ) can efficiently be sparsified to ?(?) constraints is balanced [Chen, J & Pieterse, IPEC 18] 37
Sparsification for symmetric CSPs A Boolean relation ? 0,1?is symmetric if ? ? depends only on the number of 1 s in ?, and not on the position of the 1 s in ? [Symmetric ? is characterized by the weights of the satisfying assignments] We say is symmetric if each ? is symmetric Let be a finite symmetric intractable Boolean constraint language ? with satisfying weights ?? 0, ,?? ? if ?,?,? ??, then ? ? + ? ??or ? ? + ? {0, ,?? ? } is balanced 38
Open: Optimal sparsification beyond linear Shown which symmetric Boolean allow ?(?) sparsification Beyond linear sparsification, little is known Open problem: Find a characterization of the optimal sparsification size for all finite symmetric Boolean constraint languages 39
Open: Polynomial sparsification beyond linear Shown which symmetric Boolean allow ?(?) sparsification Much remains unknown about the optimal sparsification size for some symmetric Boolean CSPs Open problem: Does Boolean CSP with unbounded-length constraints #satisfied literals is 1 or 2, mod 6 have poly. sparsification? (compression to ?(??) bits for some constant ?) Reason why current approach fails: No univariate polynomial mod 6 has {1,2} as its roots 40
Maltsev embeddings TALK LANDSCAPE
Characterizing optimal sparsification sizes Based on largest OR that ? can express in a technical sense: using constants, negations, and repetitions of variables, but without introducing fresh variables (0, (0, (0, (1, (1, (1, 0, 1, 1, 0, 0, 1, 1) 0) 1) 0) 1) 0) (1, (0, (1, 0) 1) 1) ?3???= cone-defines ? 2= ?,?,0 ?3??? ?,? ? 2 42
Characterization for low-arity CSPs Let be a finite Boolean intractable constraint language, in which each relation has arity at most three [Chen, J & Pieterse, IPEC 18] Let ? 1 be the arity of the largest OR that can cone-define. Then CSP has a sparsification with ? ??constraints, but no sparsification with ?(?? ?) constraints. (for any ? > 0, assuming NP coNP/poly) Characterizes optimal sparsification size based on easy condition The polynomial-based framework gives optimal sparsifications for all constraint languages whose relations have arity 3 43
Open: Linear sparsification or not? Result shows which Boolean of arity 3 have ?(?) sparsific. A first obstacle in a complete understanding of Boolean constraint languages that admit linear sparsification is: 1,0,0,1,1,1,0,0,1 0,0,0,0,1,0,0,1,1 0,1,0,1,1,0,1,1,0 0,0,0,1,0,1,1,0,0 0,0,1,0,0,1,1,1,1 ?OPEN= Open problem: Does CSP( ?OPEN) admit a linear sparsification? (compression to ?(?) bits) 44
Maltsev embeddings TALK LANDSCAPE
Conclusion Polynomial framework for sparsification is quite powerful Has interpretation as embedding into a tractable larger-domain CSP For Boolean CSPs, explicit characterizations are known of: Which CSP admit nontrivial sparsification Which symmetric CSP( ) admit a linear sparsification Optimal sparsification size for all constraint languages whose relations have arity 3 Open problems: Full characterization of (Boolean) CSPs with linear sparsification Sparsification complexity for non-Boolean CSPs THANK YOU! 46
