定义图灵机的时间复杂性

• DTM 在长度为 $n$ 的输入上所经过的最大步数为 $f(n)$
• NTM 在长度为 $n$ 的输入上在任何分支所经过的最大步数为 $f(n)$

则 M 的时间复杂度为 $f(n)$

定义图灵机的空间复杂性类

• P 表示所有能在多项式时间上被 DTM 接受的语言
• NP 表示所有能在多项式时间上被 NTM 接受的语言

定理：每个 $O(f(n))$ 的多带图灵机都和某一个 $O(f^2(n))$ 的单带图灵机等价

定理：每个 $O(f(n))$ 的 NTM 都和某一个 $2^{O(f(n))}$ 的 DTM 等价

定义语言 $A$ 的验证机为一个算法 $V$，$A$ 为所有的 $w$，对每个字符串 $c$，$V$ 接受 $<w,c>$

验证机用额外的信息 $c$ 来验证 $w$ 是 $A$ 的成员，这里 $c$ 被称为 $A$ 的成员证明或证书。

若 $A$ 有一个多项式时间的验证机，则称它为多项式可验证的；且它的成员证书有着多项式的长度，因为这是它时间限制内能访问的最大长度