计算复杂性理论（Computational complexity theory）研究解决计算问题需要多少资源，以及问题之间的难度关系. 常见资源包括运行时间、存储空间、随机性和并行能力.
复杂度类
复杂度理论把具有相近资源上界的问题归入复杂度类. P 类包含可由确定性算法在多项式时间内求解的判定问题；NP 类包含给定候选答案后可在多项式时间内验证的判定问题.
归约用一种问题的求解过程表达另一种问题，从而比较它们的难度. P 与 NP 问题询问这两个复杂度类是否相等，是这一领域最著名的开放问题之一.