Insights into Constraint Satisfaction Problems (CSPs) and Computational Complexity

Slide Note

Delve into the world of Constraint Satisfaction Problems (CSPs) with a focus on Boolean domain instances, computational complexity, testing assignments, and more. Learn about Schaefer's Theorem, query complexities, and characterizing constraint languages. Explore the challenges and optimism in navigating the realm of CSPs.

davenport_l Follow

Uploaded on Oct 05, 2024 | 0 Views

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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Testing Assignments of Boolean CSP s Arnab Bhattacharyya and Yuichi Yoshida DIMACS/Rutgers and National Institute for Informatics

Constraint Satisfaction Problems CSP( ) ) instance CSP instance ??,??, ,?? {?,?} Domain = {?,?} ????? ??,?? ????? ??+ ??+ ?? ??? ??,??,?? ???? ?? Constraint Language = ????? , ,????? , ??? , , ,????

Constraint Satisfaction Problems finite collection of relations on domain Set of instances defined by constraints using relations from CSP( ) Computational problem: Given instance of CSP( ), is there an assignment to the variables satisfying all constraints?

Examples ?-COLORABILITY: = { } over domain ? 2-SAT: = {?? ?,?? ?,? ? ?,? ? ?} over domain 0,1 . Similarly, ?-SAT 3-LIN over ?2 Horn 3-SAT

Computational Complexity Clearly, CSP( ) in NP for all . Schaefer s Theorem(1977): For Boolean domain, CSP( ) is NP-complete unless every instance is: 1. Satisfied by all-ones or all-zeroes assignment 2. Is a Horn-SAT or Dual Horn-SAT instance 3. Is a 2-SAT instance 4. Is a system of linear equations over ?2 Dichotomy also shown over {0,1,2} (Bulatov, 2003) and conjectured over all finite domains (Feder-Vardi, 1999)

Testing CSP assignments Can we quickly test if an assignment satisfies a CSP( ) instance? How does ? affect worst- case query complexity? Testing problem: For a parameter ? > 0 and instance ? of CSP( ) on ? variables and domain ?, INPUT: ? ?? MODEL: Query access to coordinates of ? OUTPUT: YES if ? satisfies ?, NO if ?,? > ?? for all satisfying assignments ?

Whats known? CSP( ), 2-SAT testable with (log?/loglog?), ?( ?) queries (FLNRRS 02). 3-LIN, 3-SAT require (?) queries (BHR 06) Can we characterize exactly when constraint languages over Boolean domain are sublinear-query testable?

Arent we too optimistic? Infinitely many relations, infinitely many s what structure of constraint languages can we expect to use?

Arent we too optimistic? NO Infinitely many relations, infinitely many s what structure of constraint languages can we expect to use? Turns out that we can restrict ourselves to s that naturally define an algebra. And we can use algebraic properties to classify query complexity of Boolean CSP s!

From Relations to Algebra Closed under compositions and contains projections: a clone Define Pol( ) = ? Pol(?)

Polymorphisms determine complexity Theorem (Yoshida 12): If CSP( ) is testable with ?(?,?,?) queries, then any with Pol( ) = Pol( ) is testable with ? ) ? ,? ? ,? ? ) queries. 1 ?+ ?(?( ? +

Posts Lattice Inclusion structure of Boolean clones

Main result CSP( ) Contains NU; ?(?? ?/?) 2-SAT ? 1 ??(1), log? loglog? Horn 3-SAT (?) 0-valid or 1-valid Affine NAE 3-SAT

Components of the Result Pre-existing bounds from (FLNRRS 02) , (BHR 06), and (Yoshida 12) plus: (?) lower bound for testing Horn 3-SAT instances ? ?1 1/? upper bound for testing CSP( ) when Pol( ) contains a weak near- unanimity operation

Horn 3-SAT Each constraint is a disjunctive clause of at most 3 variables with at most one positive literal: ? ? ? , ? ? ? ,? Can be solved in polynomial time by unit propagation