Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$8,593.11

Advancing SAT solving algorithms with Applications to problems in Verification and AI

EF 2023-24

Résumé
With increasing computing power comes the desire to apply computers to solve ever more complex tasks. Many of these tasks require dealing with problems that are known to be computationally intractable. This means that in the worst case no matter how much computing power we have available to us now or in the future we will not be able to solve such problems. Formally, such problems are characterized as being NP-Hard. Nevertheless, recent developments have in practical computing have not been deterred by this worst case analysis. In fact, there are many modern computing applications addressing important practical problems that routinely solve NP-Hard problems. The key this seeming contradiction is that often these practical problems possess extra structure that make them solvable. However, except for a few special cases, as yet no one has been able provide an adequate formal characterization of the features that make many practical problems solvable. As a result there are no algorithms for solving such problems with guaranteed reasonable computation times: in order to achieve such guarantees one would need to have a formal characterization of the features that ensure tractability. Instead what has proved to be successful is the development of algorithms for solving the general problem; despite the fact that the general problem is intractable. Research over the past 15 years has shown that it is often the case that techniques designed to make an algorithm more effective on the general problem end up being most effective on problems arising from practice; i.e., such techniques tend to be more effective on practical problems. An example of this is the use of clause learning in SAT solvers. This observation has motivated much of my previous research and will continue to motivate the research proposed here. In particular, my work has focused on finding techniques and algorithms for solving intractable problems by exploiting ideas designed to make the solver more effective on the general problem. That is, my research has found new algorithms and techniques for building better general purpose solvers and the effect has been that such solvers have been increasingly more effective on a range of important practical problems. The proposed research will be to find more effective techniques for solving general purpose problems, specifically MaxSat, #SAT and QBF. Many practical problems can be cast as a MaxSat, #SAT or QBF problem. Hence, once we have an effective solver for these problems we have a method for solving a range of practical problems. In addition to this fundamental research into improving solvers for these general problems the proposal is also to apply such solvers to a wider range of practical problems arising in the areas of AI and formal verification. Some work has already been accomplished on this aspect of the research and the proposal involves accomplishing more.
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
RGPIN-2016-05527
Name nom
Bacchus, Fahiem
Department département
Head Office
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2016
Award amount
8593.11
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
801
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
Computer software
Area of application fr
Logiciel
Research subject code
2803
Research subject group en
Artificial intelligence
Research subject group fr
Knowledge representation
Research subject en
Intelligence artificielle
Research subject fr
Répresentation des connaissances
Application title
Advancing SAT solving algorithms with Applications to problems in Verification and AI
Keyword
Integer Programming; Matchings in Economic Settings; MaxSat Solvers; Minimal Unsatisfiable Sets; Sat solvers; Synthesis
Application summary
With increasing computing power comes the desire to apply computers to solve ever more complex tasks. Many of these tasks require dealing with problems that are known to be computationally intractable. This means that in the worst case no matter how much computing power we have available to us now or in the future we will not be able to solve such problems. Formally, such problems are characterized as being NP-Hard. Nevertheless, recent developments have in practical computing have not been deterred by this worst case analysis. In fact, there are many modern computing applications addressing important practical problems that routinely solve NP-Hard problems. The key this seeming contradiction is that often these practical problems possess extra structure that make them solvable. However, except for a few special cases, as yet no one has been able provide an adequate formal characterization of the features that make many practical problems solvable. As a result there are no algorithms for solving such problems with guaranteed reasonable computation times: in order to achieve such guarantees one would need to have a formal characterization of the features that ensure tractability. Instead what has proved to be successful is the development of algorithms for solving the general problem; despite the fact that the general problem is intractable. Research over the past 15 years has shown that it is often the case that techniques designed to make an algorithm more effective on the general problem end up being most effective on problems arising from practice; i.e., such techniques tend to be more effective on practical problems. An example of this is the use of clause learning in SAT solvers. This observation has motivated much of my previous research and will continue to motivate the research proposed here. In particular, my work has focused on finding techniques and algorithms for solving intractable problems by exploiting ideas designed to make the solver more effective on the general problem. That is, my research has found new algorithms and techniques for building better general purpose solvers and the effect has been that such solvers have been increasingly more effective on a range of important practical problems. The proposed research will be to find more effective techniques for solving general purpose problems, specifically MaxSat, #SAT and QBF. Many practical problems can be cast as a MaxSat, #SAT or QBF problem. Hence, once we have an effective solver for these problems we have a method for solving a range of practical problems. In addition to this fundamental research into improving solvers for these general problems the proposal is also to apply such solvers to a wider range of practical problems arising in the areas of AI and formal verification. Some work has already been accomplished on this aspect of the research and the proposal involves accomplishing more.