Computational complexity of polynomial time problems

复杂性理论的目标是根据解决问题所需的资源量，对计算机可解决的问题进行严格的分类。计算时间被认为是一种资源，以及内存、处理器、随机比特、通信比特等。复杂性理论的方法论依赖于抽象计算机模型的定义，依赖于在这种模型上解决问题的算法的开发，并且(理想地)依赖于所找到的算法是可能的最佳的数学证明。在某些情况下，这样的证明将具有巨大的实用价值；例如，将一个大数因式分解成两个较小的数并乘以这个数的困难是当今密码学的主要基础。我的研究的主要长期目标是在阐明可在多项式时间内求解的复杂P类问题的结构方面取得进展。特别是，我将继续致力于是否可以仅使用对数内存量执行任意多项式时间计算的问题。这是一个有35年历史的悬而未决的问题，它暗示了复杂性理论的主要缺陷：尽管一代研究人员付出了大量的努力，但人们对复杂性类NP中特定问题的复杂性的显著下界知之甚少。我工作的短期目标是使用复杂性理论的工具，通过(A)将这种复杂性与其他研究得很好的问题的复杂性进行比较，(B)证明受限计算模型的下界，以及(C)进一步研究代数、逻辑和复杂性之间的联系，来更好地理解特定问题的复杂性。具体而言，我的工作是通过(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.