计算复杂性（computational complexity）理论是计算机科学的重要组成部分，同时也是密码学的理论基础之一，它提供了一种分析不同密码技术和算法的计算复杂性方法。一个算法的复杂性是指运算改算法所需的计算能力。算法的计算复杂性通常用时间复杂性T和空间复杂性S来度量。

 算法可以分为多项式时间（polynomial-time）算法、指数（exponential）算法和超多项式（superpoly-nomial）算法三类。具有多项式时间复杂性的算法族，其复杂性可表示为O(n^m)，其中是一个常数。具有指数时间复杂性的算法族，其时间复杂性可表示为O(t^f(n))，这里，t是一个大于1的常数，f(n)为n的多项式函数。超多项式算法族的复杂性的复杂性可表示为O(r^f(n))，其中r是一个常数，f(n)是大于常数而小于线性的函数。

  概况的讲，计算机可以在多项式时间内解决的问题称为P类问题，计算机在多项式时间复杂度内不可以解决的问题称为NP类问题。P类问题是计算机能计算的，而NP类问题是计算机不能计算的，即NP类问题是一类困难问题。NP类问题中最困难的一类问题称为NP-完全问题，简称NPC问题。

 下面给出P, NP与NP-完全的形式化定义：

   复杂度类P：如果存在一种确定性的图灵机M和一个多项式p(▪)，并且满足：

    • 当输入字符串x时，M机器至多在p（|x|）步以后停止；

   • M（x）=1当且仅当x∈L。

   则称P是在（确定性）多项式时间内可识别的一类语言。

  惯例上将NP定义为可被非确定性的多项式时间图灵机识别语言类型。

   NP-完全：如果一种语言是NP的，且每一种NP语言关于它都是多项式可约的，那么这种语言就是NP-完全的。