Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$52,000.00

SAT and beyond, new algorithms for fundamental reasoning problems

EF 2007-08

Résumé
The proposed research will mainly focus on developing new algorithms and techniques for solving the Satisfiability problem and its extensions. A wide range of fundamental and practical problems in Artificial Intelligence, and in Computer Science in general, can be cast as instances of satisfiability (SAT). This is not surprising since SAT is the canonical NP-Complete problem. What is surprising is that despite its worst case complexity, the most effective way to solve a variety of practical problem is to cast them as SAT and then solve the resulting SAT problem with a state of the art SAT solver. For example, many problems in hardware verification are now best solved using SAT technology. There are also a number of useful generalizations of SAT. Two particularly important generalizations are #SAT, the problem of counting the number of satisfying models, and QBF (Quantified Boolean Formulas), which is like SAT except that some of the variables can be universally quantified. These generalizations cover an even wider range of important practical problems. For example, the problem of inference in Bayesian Networks can be cast as a weighted #SAT problem (where each satisfying model has a different weight). The proposed research program will focus on developing new and better general algorithms for solving these core satisfiability problems: SAT, QBF, and #SAT (in both its weighted and unweighted versions). It will build on previous work by the applicant. This previous work has already been successful in achieving significant advances in the state of the art, and in our fundamental understanding of these problems. Nevertheless many important and subtle problems remain. Addressing these problems will be the main focus of the applicant's research activities. This research will contain many opportunities for the training of highly qualified personnel.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
41848-2006
Name nom
Bacchus, Fahiem
Department département
Computer Science
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2007
Competition year année de concours
2006
Award amount
52000
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
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
2803
Research subject group en
Artificial intelligence
Research subject group fr
Intelligence artificielle
Research subject en
Knowledge representation
Research subject fr
Répresentation des connaissances
Partie
2
Nb partie
5
Application title
SAT and beyond, new algorithms for fundamental reasoning problems
Keyword
NA
Application summary
The proposed research will mainly focus on developing new algorithms and techniques for solving the Satisfiability problem and its extensions. A wide range of fundamental and practical problems in Artificial Intelligence, and in Computer Science in general, can be cast as instances of satisfiability (SAT). This is not surprising since SAT is the canonical NP-Complete problem. What is surprising is that despite its worst case complexity, the most effective way to solve a variety of practical problem is to cast them as SAT and then solve the resulting SAT problem with a state of the art SAT solver. For example, many problems in hardware verification are now best solved using SAT technology. There are also a number of useful generalizations of SAT. Two particularly important generalizations are #SAT, the problem of counting the number of satisfying models, and QBF (Quantified Boolean Formulas), which is like SAT except that some of the variables can be universally quantified. These generalizations cover an even wider range of important practical problems. For example, the problem of inference in Bayesian Networks can be cast as a weighted #SAT problem (where each satisfying model has a different weight). The proposed research program will focus on developing new and better general algorithms for solving these core satisfiability problems: SAT, QBF, and #SAT (in both its weighted and unweighted versions). It will build on previous work by the applicant. This previous work has already been successful in achieving significant advances in the state of the art, and in our fundamental understanding of these problems. Nevertheless many important and subtle problems remain. Addressing these problems will be the main focus of the applicant's research activities. This research will contain many opportunities for the training of highly qualified personnel.