The computational complexity of polynomial time problems

多项式时间问题的计算复杂度

• 批准号: 9979-2012
• 负责人: McKenzie, Pierre
• 金额: $ 1.6万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=568694
• 关键词: computational; complexity; polynomial; time; problems

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).

复杂性理论旨在根据解决问题所需的资源数量，对计算机可解决的问题进行严格的分类。计算时间被认为是一种资源，以及内存、处理器、随机比特、通信比特等。复杂性理论的方法论依赖于抽象计算机模型的定义，依赖于在这种模型上解决问题的算法的开发，并且(理想地)依赖于所找到的算法是可能的最佳的数学证明。在某些情况下，这样的证明将具有很大的实用价值；例如，今天实际使用的密码协议的安全性取决于人们认为的--但尚未证明--计算问题的难度，例如将一个大数字分解成两个更小的数字，然后再乘以这个数字。 我研究的长期目标是在阐明在多项式时间内可解的复杂P类问题的结构方面取得进展。特别是，我感兴趣的是40年前的一个悬而未决的问题，即P中的每个问题是否都可以仅使用对数内存量就能解决。这个问题和其他类似的问题暗示了复杂性理论的主要缺陷：尽管一代研究人员进行了大量的努力，但在复杂性类NP(一个假设大于P的类)中，关于特定问题的复杂性的令人满意的下界知之甚少。 我的短期目标是通过(A)将这种复杂性与其他研究得很好的问题的复杂性进行比较，(B)证明受限计算模型的下界，以及(C)进一步研究代数、逻辑和复杂性之间的联系，来确定特定问题的复杂性。人们希望，理解受限计算模型的力量，并以不同的方式描述后者，将有助于开发最终能够解决直接实际问题(如因式分解)的证明技术。