Computational complexity of polynomial time problems

点击翻译按钮获取中文摘要

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.