Grant: Discovery Grants Program - Individual
Simon Fraser University
$43,000.00
The complexity of the constraint satisfaction problem and its variants
FY 2015-16
Summary
The constraint satisfaction problem (CSP) provides a general framework in which it is possible to express, in a natural way, a wide variety of problems. The aim in a CSP is to find an assignment of values to a given set of variables, subject to constraints on the values which can be simultaneously assigned to certain specified subsets of variables; in the counting constraint satisfaction problem the objective is to find the number of such assignments. The CSP is therefore very important in a number of applications, both theoretical and practical. In theoretical applications we look for new algorithmic ideas that can help to solve problems that could not be solved before, to improve the existing algorithms, to design more general and uniform algorithms, and to find evidence that certain problems are not efficiently solvable in the general case. In practical applications, constraint and satisfiability solvers are now standard tools in a wide range of areas from scheduling to hardware verification. Advances in the study of the CSP will speed up such solvers and expand their area of applicability.
This project will contribute in both aspects of constraint problems, although its main focus is on the theoretical side. One of its main goals is to precisely understand which CSPs can be solved efficiently and design an efficient solution algorithm. This is one of the long standing open problems in computer science, but there is evidence that we may be approaching its resolution. Another component of the project is the study of counting constraint satisfaction problems. This area has unlikely connections to statistical physics, where such numbers affect the properties of large ensembles of particle, and, in particular, help to locate phase transition thresholds, at which, for instance, liquid turns to gas. Finally, this project proposes to study the efficiency and to design new algorithms in the framework that is closer to practical circumstances than the standard worst case approach. It is known that practical problems tend to have a certain property called the power law distribution, and we plan to mathematically study the behaviour of various algorithms on instance of the CSP satisfying this property.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2015-04656
Name nom
Bulatov, Andrei
Department département
Computing Science, School of - Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2015
Competition year année de concours
2015
Award amount
43000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
The complexity of the constraint satisfaction problem and its variants
Keyword
NSERC
Application summary
<p>The constraint satisfaction problem (CSP) provides a general framework in which it is possible to express, in a natural way, a wide variety of problems. The aim in a CSP is to find an assignment of values to a given set of variables, subject to constraints on the values which can be simultaneously assigned to certain specified subsets of variables; in the counting constraint satisfaction problem the objective is to find the number of such assignments. The CSP is therefore very important in a number of applications, both theoretical and practical. In theoretical applications we look for new algorithmic ideas that can help to solve problems that could not be solved before, to improve the existing algorithms, to design more general and uniform algorithms, and to find evidence that certain problems are not efficiently solvable in the general case. In practical applications, constraint and satisfiability solvers are now standard tools in a wide range of areas from scheduling to hardware verification. Advances in the study of the CSP will speed up such solvers and expand their area of applicability.</p>
<p> This project will contribute in both aspects of constraint problems, although its main focus is on the theoretical side. One of its main goals is to precisely understand which CSPs can be solved efficiently and design an efficient solution algorithm. This is one of the long standing open problems in computer science, but there is evidence that we may be approaching its resolution. Another component of the project is the study of counting constraint satisfaction problems. This area has unlikely connections to statistical physics, where such numbers affect the properties of large ensembles of particle, and, in particular, help to locate phase transition thresholds, at which, for instance, liquid turns to gas. Finally, this project proposes to study the efficiency and to design new algorithms in the framework that is closer to practical circumstances than the standard worst case approach. It is known that practical problems tend to have a certain property called the power law distribution, and we plan to mathematically study the behaviour of various algorithms on instance of the CSP satisfying this property.</p>