Computational complexity of polynomial time problems

复杂性理论的目标是根据解决问题所需的资源数量对计算机可解决的问题进行严格的分类。计算时间被认为是一种资源，以及存储器，处理器，随机位，通信位等复杂性理论的方法论依赖于抽象计算机模型的定义，解决此类模型问题的算法的发展，以及（理想情况下）找到的算法是最好的数学证明。在某些情况下，这样的证明会有很大的实用价值;例如，将一个大的数字分解成两个小的数字，再乘以这个数字，这类问题的难度是当今密码学的基础。我研究的主要长期目标是在阐明可在多项式时间内解决的问题的复杂性类P的结构方面取得进展。特别是，我将继续致力于一个任意的多项式时间计算是否可以只使用对数数量的内存执行的问题。这是一个有35年历史的公开问题，它暗示了复杂性理论的主要缺点：尽管一代研究人员付出了巨大的努力，在复杂性类NP中，关于特定问题的复杂性的重要下界很少。我工作的短期目标是使用复杂性理论的工具，通过（A）更好地理解特定问题的复杂性。将这种复杂性与其他研究得很好的问题进行比较，（B）证明限制计算模型的下界，（C）进一步研究代数，逻辑和复杂性之间的联系。特别是，我将进一步发展和研究介于单调布尔电路，的显着的下界是已知的，和一般的布尔电路，其中的下界大多是不存在的。新的模型包括语义增量分支程序，最近推出的，并建议推广的单调跨度计划，取代平等的不平等约束。研究这些新模型为扩展当前的证明技术提供了希望，从而更接近于能够确定直接实际感兴趣的问题的复杂性。

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.