Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Université de Montréal

$22,000.00

The computational complexity of polynomial time problems

FY 2017-18

Summary
Complexity theory aims at rigorously classifying problems solvable by computers on the basis of the amounts of resources needed to solve them. Computing time is considered as a resource, as well as memory, processors, random bits, communication bits, etc. The methodology of complexity theory rests on the definition of abstract computer models, on the development of algorithms solving a problem on such models, and (ideally) on the mathematical proof that the algorithms found are the best possible. In some cases, such a proof would have great practical value; for example, the security of cryptographic protocols in actual use today rests on the perceived --but as yet unproven-- difficulty of computational problems such as factoring a large number into two smaller numbers that multiply out to this number.The long-term goal of my research is to make progress towards elucidating the structure of the complexity class P of problems solvable in polynomial time. In particular, I'm interested in the 40 year-old open question of whether every problem in P can be solved using only a logarithmic amount of memory. That question and others like it hint at the main shortcoming of complexity theory: despite intensive efforts by a generation of researchers, very few satisfactory lower bounds on the complexity of specific problems within the complexity class NP (a class presumably larger than P) are known.My short-term goal is to determine the complexity of specific problems by (A) comparing this complexity with that of other well-studied problems, (B) proving lower bounds on restricted models of computation and (C) further investigating the connections between algebra, logic and complexity. The hope is that understanding the power of restricted models of computation and characterizing the latter in different ways will help developing proof technology that can eventually tackle problems of immediate practical concern (such as factoring).
Program
Discovery Grants Program - Individual
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
9979-2012
Name nom
McKenzie, Pierre
Department département
Informatique et recherche opérationnelle
Organization id
63
Institution établissement
Université de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2012
Award amount
22000
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
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
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Partie
5
Nb partie
5
Application title
The computational complexity of polynomial time problems
Keyword
NSERC
Application summary
Complexity theory aims at rigorously classifying problems solvable by computers on the basis of the amounts of resources needed to solve them. Computing time is considered as a resource, as well as memory, processors, random bits, communication bits, etc. The methodology of complexity theory rests on the definition of abstract computer models, on the development of algorithms solving a problem on such models, and (ideally) on the mathematical proof that the algorithms found are the best possible. In some cases, such a proof would have great practical value; for example, the security of cryptographic protocols in actual use today rests on the perceived --but as yet unproven-- difficulty of computational problems such as factoring a large number into two smaller numbers that multiply out to this number.The long-term goal of my research is to make progress towards elucidating the structure of the complexity class P of problems solvable in polynomial time. In particular, I'm interested in the 40 year-old open question of whether every problem in P can be solved using only a logarithmic amount of memory. That question and others like it hint at the main shortcoming of complexity theory: despite intensive efforts by a generation of researchers, very few satisfactory lower bounds on the complexity of specific problems within the complexity class NP (a class presumably larger than P) are known.My short-term goal is to determine the complexity of specific problems by (A) comparing this complexity with that of other well-studied problems, (B) proving lower bounds on restricted models of computation and (C) further investigating the connections between algebra, logic and complexity. The hope is that understanding the power of restricted models of computation and characterizing the latter in different ways will help developing proof technology that can eventually tackle problems of immediate practical concern (such as factoring).