Computational complexity of polynomial time problems

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

• 批准号: 9979-2007
• 负责人: McKenzie, Pierre
• 金额: $ 2.77万
• 依托单位: Université de Montréal
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=364851
• 关键词: Computational; complexity; 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.

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