The computational complexity of polynomial time problems

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

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

复杂性理论旨在根据解决问题所需的资源数量对计算机可解决的问题进行严格分类。计算时间被认为是一种资源，以及存储器，处理器，随机位，通信位等复杂性理论的方法论依赖于抽象计算机模型的定义，解决此类模型问题的算法的发展，以及（理想情况下）找到的算法是最好的数学证明。在某些情况下，这样的证明将具有很大的实用价值;例如，今天实际使用的密码协议的安全性取决于可感知的-但尚未证明-计算问题的难度，例如将一个大的数字分解为两个较小的数字，然后乘以这个数字。