Grant: Discovery Grants Program - Individual
Université de Montréal
$38,000.00
Computational complexity of polynomial time problems
FY 2008-09
Summary
The goal of complexity theory is to rigorously classify 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 perceived -but as yet unproven- difficulty of problems such as factoring a large number into two smaller numbers that multiply out to this number underlies much of today's cryptography.
The main long-term goal of my research is to make progress in elucidating the structure of the complexity class P of problems solvable in polynomial time. In particular, I will continue to devote effort to the question of whether an arbitrary polynomial time computation can be performed using only a logarithmic amount of memory. This is a 35 year-old open question, and it hints at the main shortcoming of complexity theory : despite intensive efforts by a generation of researchers, very few significant lower bounds on the complexity of specific problems within the complexity class NP are known.
The short-term goal of my work is to use the tools of complexity theory to better understand the complexity of specific problems by (A) comparing this complexity with those 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.
In particular, I will further develop and investigate models of computation that are intermediate between the monotone Boolean circuit, for which significant lower bounds are known, and general Boolean circuits, for which lower bounds are mostly inexistant. The new models include the semantic incremental branching program, recently introduced, and a proposed generalisation of monotone span programs which replaces equality constraints by inequalities. Studying such new models offers hope to extend current proof technology and thus move closer to being able to determine the complexity of problems of immediate practical interest.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
9979-2007
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
2008
Competition year année de concours
2007
Award amount
38000
Program id
RGPIN
Program nane 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
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
Computational complexity of polynomial time problems
Keyword
NA
Application summary
The goal of complexity theory is to rigorously classify 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 perceived -but as yet unproven- difficulty of problems such as factoring a large number into two smaller numbers that multiply out to this number underlies much of today's cryptography.
The main long-term goal of my research is to make progress in elucidating the structure of the complexity class P of problems solvable in polynomial time. In particular, I will continue to devote effort to the question of whether an arbitrary polynomial time computation can be performed using only a logarithmic amount of memory. This is a 35 year-old open question, and it hints at the main shortcoming of complexity theory : despite intensive efforts by a generation of researchers, very few significant lower bounds on the complexity of specific problems within the complexity class NP are known.
The short-term goal of my work is to use the tools of complexity theory to better understand the complexity of specific problems by (A) comparing this complexity with those 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.
In particular, I will further develop and investigate models of computation that are intermediate between the monotone Boolean circuit, for which significant lower bounds are known, and general Boolean circuits, for which lower bounds are mostly inexistant. The new models include the semantic incremental branching program, recently introduced, and a proposed generalisation of monotone span programs which replaces equality constraints by inequalities. Studying such new models offers hope to extend current proof technology and thus move closer to being able to determine the complexity of problems of immediate practical interest.