主题
根据问题解决的难易程度对问题进行分类的理论。如果解决一个问题所需的步骤数受问题规模的某个幂次方限制，则该问题被归为 P 问题（多项式时间）类。如果一个问题允许非确定性解法，并且验证解法所需的步骤数受问题规模的某个幂次方限制，则该问题被归为 NP 问题（非确定性多项式时间）类。P 问题类是 NP 问题类的子集，但也存在不属于 NP 的问题。
目前还没有已知的用于图同构测试的 P 算法，尽管该问题也尚未被证明是 NP 完全的。事实上，如果 P 和 NP 完全之间存在裂缝，那么识别同构图的问题似乎就落在这条裂缝中（Skiena 1990，p. 181），因此，这个问题有时被归为特殊的图同构完全复杂性类。
如果已知 NP 问题的解，则可以将其简化为单个多项式时间验证。如果一个问题是 NP 问题，并且解决它的算法可以转化为解决任何其他 NP 问题的算法，则该问题是 NP 完全的。NP 完全问题的例子包括哈密顿回路和旅行商问题。线性规划曾被认为是 NP 问题，但 L. Khachian 在 1979 年证明它实际上是一个 P 问题。尚不清楚是否所有表面上是 NP 问题的问题实际上都是 P 问题。
Goetz, P. "Phil Goetz's Complexity Dictionary." http://www.cs.buffalo.edu/~goetz/dict.htmlGriffor, E. R. (Ed.). 可计算性理论手册。 Amsterdam, Netherlands: Elsevier, 1999.Hopcroft, J. E. and Ullman, J. D. 自动机理论、语言和计算导论。 Reading, MA: Addison-Wesley, 1979.Lewis, H. R. and Papadimitriou, C. H. 计算理论要素，第二版。 Englewood Cliffs, NJ: Prentice-Hall, 1997.Skiena, S. 离散数学实现：组合数学和图论与 Mathematica。 Reading, MA: Addison-Wesley, 1990.Sudkamp, T. A. 语言和机器：计算机科学理论导论，第二版。 Reading, MA: Addison-Wesley, 1996.Weisstein, E. W. "计算复杂性书籍。" http://www.ericweisstein.com/encyclopedias/books/ComputationalComplexity.html.Welsh, D. J. A. 复杂性：结、着色和计数。 New York: Cambridge University Press, 1993.Weisstein, Eric W. "复杂性理论。" 来自 Web 资源。 https://mathworld.net.cn/ComplexityTheory.html