Algorithms and Complexity of Constraint Satisfaction Problems

• Applicant: Dr. Marc Thurley
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 195373576

Constraint satisfaction problems (CSP) form a general framework for formulating algorithmic problems. The goal in a constraint satisfaction problem is to assign values to given variables such that certain constraints are satisfied. A wide variety of problems can be formulated quite naturally in this way, for example, propositional satisfiability (SAT), graph colorability and planning problems. By its generality, constraint satisfaction is ubiquitous in several areas such as database theory and artificial intelligence. In complexity theory, the study of tractable cases of CSP is of prominent importance.The research proposed consists of two parts studying different aspects of constraint satisfaction. The first part proposes an in-depth study of the capabilities of specialized algorithmic approaches to constraint satisfaction problems. The second part aims at studying the complexity of large classes of constraint satisfaction problems especially with respect to the complexity of counting in constraint satisfaction.

• DFG Programme: Research Fellowships
• International Connection: Spain
• Host: Professor Albert Atserias