Computational complexity of 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.