Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Toronto

$29,000.00

Logic and computational complexity

FY 2014-15

Summary
The principal aim of my research is to understand the limitations of computer programs in solving certain important types of problems. These problems are ones where there are a certain number of conditions to be satisfied; assuming a given collection of conditions, it is easy to check whether or not a proposed solution is in fact correct, but it appears to be difficult to search for a solution. An everyday example of this kind of problem is provided by puzzles, such as jigsaw puzzles, or the problem of solving Rubik's Cube. These type of problems are in the category NP. Of these, the best known is the Satisfiability problem from logic, which is the problem of whether a formula of propositional logic has a satisfying assignment.The main goal is to show that such problems, and in particular the Satisfiability problem, are hard to solve in general. In the case where a satisfiability problem has no solution, we can demonstrate this by providing a proof in a logical system. If we can show that in certain cases, where the problems are complicated, that the proofs of unsatisfiability must be exponentially long, then this shows that certain algorithms for the problem must take an exponentially long time in the worst case. This has already been shown for the best known and most successful algorithm for satisfiability, the resolution method. I hope in my research to extend these results to more powerful logical systems, and hence to broader classes of algorithms.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
105666-2011
Name nom
Urquhart, Alasdair
Department département
Computer Science (St. George Campus)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2014
Competition year année de concours
2011
Award amount
29000
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
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
2703
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Complexity
Research subject fr
Complexité
Partie
4
Nb partie
5
Application title
Logic and computational complexity
Keyword
NSERC
Application summary
The principal aim of my research is to understand the limitations of computer programs in solving certain important types of problems. These problems are ones where there are a certain number of conditions to be satisfied; assuming a given collection of conditions, it is easy to check whether or not a proposed solution is in fact correct, but it appears to be difficult to search for a solution. An everyday example of this kind of problem is provided by puzzles, such as jigsaw puzzles, or the problem of solving Rubik's Cube. These type of problems are in the category NP. Of these, the best known is the Satisfiability problem from logic, which is the problem of whether a formula of propositional logic has a satisfying assignment.The main goal is to show that such problems, and in particular the Satisfiability problem, are hard to solve in general. In the case where a satisfiability problem has no solution, we can demonstrate this by providing a proof in a logical system. If we can show that in certain cases, where the problems are complicated, that the proofs of unsatisfiability must be exponentially long, then this shows that certain algorithms for the problem must take an exponentially long time in the worst case. This has already been shown for the best known and most successful algorithm for satisfiability, the resolution method. I hope in my research to extend these results to more powerful logical systems, and hence to broader classes of algorithms.