Classifying the complexity of constraint satisfaction problems

Andrei Krokhin
University of Warwick, UK

The constraint satisfaction problem (CSP) is a general framework that appears in many areas of theoretical computer science and artificial intelligence. For example, it comprises the satisfiability problem from propositional logic, the homomorphism problem, conjunctive query evaluation from database theory, and many problems from graph theory.

In this talk, I will give an overview of various versions of CSP,and I will discuss approaches to classifying the complexity of this problem that use methods from logic, algebra, and discrete mathematics.

Seminar Outline compiled by Enric Guaus:

Introduction:

A constraint satisfaction problem (CSP) is a way of expressing simultaneous requirements for values of variables.  Then, the CSP can be found in so many different cognition fields such as computer science, biotechnology... This talk deals on the classification of different CSP, according to their complexity and the applied methods.

The session started with the explanation of two well known problems:

• Given a propositional formula  F =  (¬x U y U ¬z); is it satisfiable?
• Given some linear equations 2x+y-z=1 // 3x-y-3z=0 // 4x-4y+z=-3;  which are the constraints for certain variables?

Then, different points of view for solving these (and other) constrain problems were studied, as shown below

CSP in AI setting:

Let's define:

• V: Variables
• D: Values
• C: Constraints
  

then:

• C_i is (S_i, g_i)

Explanation: The constrains (C_i)  are formed by a list of variables (S_i) and m^th relationships over D

CSP in Logical setting:

If we have an instance:

• Y(x₁,x₂,...)=g₁(S₁)*...*g_q(S_q)

and a question:

• Is Y satisfiable?

then:

• SCP generalizes SATISFIABILITY

Explanation: In a logical setting, we can test if a given instance is satisfiable. SCP is a generalization of this framework.

CSP in Database setting:

If we have an instance: A structure ß (relational database) and a Query  ø according to

• y(x1,x2,...)=EXIST( x_n+1 ) ... EXIST( x_n+m ) (g₁(S₁) * ... * g_q(S_q))
• Y(ß)={(b₁...b_n)|ß=Y(b₁,...,b_n)}

and a question:

• Is Y(ß) non empty?

then:

• SCP generalizes NON EMPTY

Explanation: In a relational database setting,  we can test if a given query is non empty. SCP is a generalization of this framework.

CSP in combinational setting:

If we have an instance:

• A=(A;R₁^A,...,R_k^A)
• B=(B;R₁^B,...,R_k^B)

and a question:

• Is there any homomorphism A→B ?

then:

• SCP generalizes GRAPH HOMOMORPHISM

Explanation: In a combinational setting, we can test if two different algebraic structures are related. SCP is a generalization of this framework.

Restricting the problem

As we have seen, CSP is a very general framework. Let's focus on the homomorphism problem. This can be studied from two different points of view: the classical homomorphism  methods and the application of restricted relation CSP. In this last case, many dichotomies and theorems have to be defined .

Dichotomies & Theorems

A large list of theorems, conjectures and dichotomies were commented in this talk. Here there are some of them:

• Theorem 1: If P!=NP → there exists infinitely many complexity classes P and NP
• Conjecture 1: Then, every problem CSP(ß) is either or NP-complete

• Theorem 2: Let H be undirected graph without loops. If it is bipartite, then CSP(H) is tractable. Otherwise, CSP(H) is NP-complete

• Theorem 3: Solving systems of equations over a finite group G is tractable if G is abelian. Otherwise, it is NP-complete

• Theorem 4: Let B be a boolean structure. CSP(B) is tractable if all relations in B satisfy one of the followings conditions:

• 0-valid
• Horn
• Bijunctive
• Affine

Otherwise, CSP(B) is NP-complete

Links & References