The computational complexity of 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.