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.