多項式時間
Aをアルゴリズムとする。Aが以下の性質を満たす時、Aは多項式時間アルゴリズムであるという
ある多項式l(k)があって、任意のkと任意のkビットのデータxに対し、Aにxを入力した時にAが停止するまでのステップ数はl(k)以下である。
なお「多項式時間アルゴリズム」と言った場合、決定的アルゴリズムのみを多項式時間アルゴリズムとして認める場合と、確率的アルゴリズムをも許す場合とがある。
決定的な多項式時間アルゴリズム(上で定義した)で解ける判定問題の集合をクラスPと呼ぶ(判定問題以外の問題はクラスPに含まれないことに注意)。