Computational complexity of polynomial time problems

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

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

复杂性理论的目标是根据解决问题所需的资源量，对计算机可解决的问题进行严格的分类。计算时间被认为是一种资源，以及内存、处理器、随机比特、通信比特等。复杂性理论的方法论依赖于抽象计算机模型的定义，依赖于在这种模型上解决问题的算法的开发，并且(理想地)依赖于所找到的算法是可能的最佳的数学证明。在某些情况下，这样的证明具有很大的实用价值；例如，将一个大数字分解成两个更小的数字，然后再乘以这个数字，这样的问题被认为是困难的，但尚未得到证实，这是当今密码学的主要基础。