Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Université Laval

$24,000.00

Towards a finer classification of the complexity of constraint satisfaction problems

EF 2012-13

Résumé
The main objective of the proposal is the continued study of the computational complexity of constraint satisfaction problems (CSP). CSP offer a unified framework to analyze a wide variety of computational problems that occur naturally in many areas of computer science, most notably in artificial intelligence, database theory and combinatorial optimization. Over the last ten years, a vast research program has sought to develop the tools required to distinguish between cases of CSP solvable in polynomial time from those which are NP-complete and thus unlikely to be solvable efficiently. This research has been driven by two complementary approaches based respectively on logic and algebra. The present proposal aims to further the interaction between these two approaches and to initiate a more fine-grained analysis of the complexity of CSP. Indeed, among CSP solvable in polynomial time, one can further distinguish those computable in models with even tighter resource constraints. For CSP over the boolean domain it is for instance known that every non-trivial CSP is complete for one of the complexity classes Logspace, non-deterministic logspace, parity-counting-logspace, polynomial time (P) or NP. The long-term objective is to precisely classify the computational complexity of any subcase of CSP. I intend to build on my recent work which used the algebraic approach to obtain promising initial results in that respect. The logical approach to CSP has tied the existence of efficient algorithms for subcases of CSP with the expressibility of that CSP in a particular fragment of the database-theory inspired logic-programming language Datalog and some of its fragments. In particular, my co-authors and I recently introduced ""symmetric Datalog"" and demonstrated its connection with CSP solvable in logarithmic space. As a short term objective, I want to further understand the expressive power of symmetric Datalog and potentially, characterize it algebraically.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
312397-2008
Name nom
Tesson, Pascal
Department département
Informatique et de génie logiciel
Organization id
51
Institution établissement
Université Laval
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2008
Award amount
24000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
Research subject code
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Partie
5
Nb partie
5
Application title
Towards a finer classification of the complexity of constraint satisfaction problems
Keyword
NSERC
Application summary
The main objective of the proposal is the continued study of the computational complexity of constraint satisfaction problems (CSP). CSP offer a unified framework to analyze a wide variety of computational problems that occur naturally in many areas of computer science, most notably in artificial intelligence, database theory and combinatorial optimization. Over the last ten years, a vast research program has sought to develop the tools required to distinguish between cases of CSP solvable in polynomial time from those which are NP-complete and thus unlikely to be solvable efficiently. This research has been driven by two complementary approaches based respectively on logic and algebra. The present proposal aims to further the interaction between these two approaches and to initiate a more fine-grained analysis of the complexity of CSP. Indeed, among CSP solvable in polynomial time, one can further distinguish those computable in models with even tighter resource constraints. For CSP over the boolean domain it is for instance known that every non-trivial CSP is complete for one of the complexity classes Logspace, non-deterministic logspace, parity-counting-logspace, polynomial time (P) or NP. The long-term objective is to precisely classify the computational complexity of any subcase of CSP. I intend to build on my recent work which used the algebraic approach to obtain promising initial results in that respect. The logical approach to CSP has tied the existence of efficient algorithms for subcases of CSP with the expressibility of that CSP in a particular fragment of the database-theory inspired logic-programming language Datalog and some of its fragments. In particular, my co-authors and I recently introduced ""symmetric Datalog"" and demonstrated its connection with CSP solvable in logarithmic space. As a short term objective, I want to further understand the expressive power of symmetric Datalog and potentially, characterize it algebraically.