Grant: Discovery Grants Program - Individual
University of Toronto
$31,000.00
Logic and computational complexity
FY 2007-08
Summary
The main aim of the research is to understand why certain problems are difficult to solve using computers. Typical of such problems are those in which a certain number of simple constraints must be satisfied, as in constructing schedules. The characteristic feature of such problems (known by the technical name of NP-complete problems), is that a solution, if found, is easy to check, but deciding whether or not such a solution exists in the worst case requires an exponentially long time relative to the size of the input. The principal aim of the theory of complexity theory is to decide whether or not such problems, that seem to require exponentially long computation times in the worst case, really do require such times. My own research aims to work towards showing that exponentially long times are in fact required in the worst case by proving lower bounds on the length of certain kinds of proofs. Since a computation showing that a solution doesn't exist can be considered as a proof of a kind, lower bounds on the length of proofs show that certain kinds of algorithms (including the algorithms most often used in practice to solve such problems) cannot be efficient in the worst case.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
105666-2006
Name nom
Urquhart, Alasdair
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
31000
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
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
2
Nb partie
5
Application title
Logic and computational complexity
Keyword
NA
Application summary
The main aim of the research is to understand why certain problems are difficult to solve using computers. Typical of such problems are those in which a certain number of simple constraints must be satisfied, as in constructing schedules. The characteristic feature of such problems (known by the technical name of NP-complete problems), is that a solution, if found, is easy to check, but deciding whether or not such a solution exists in the worst case requires an exponentially long time relative to the size of the input. The principal aim of the theory of complexity theory is to decide whether or not such problems, that seem to require exponentially long computation times in the worst case, really do require such times. My own research aims to work towards showing that exponentially long times are in fact required in the worst case by proving lower bounds on the length of certain kinds of proofs. Since a computation showing that a solution doesn't exist can be considered as a proof of a kind, lower bounds on the length of proofs show that certain kinds of algorithms (including the algorithms most often used in practice to solve such problems) cannot be efficient in the worst case.