神託機械
クラス A のアルゴリズムにクラス B の問題を解くオラクルを組み合わせることで解ける決定問題の複雑性クラスを A と表記する。例えば、決定性チューリングマシンにNPクラスのオラクルが付属したもので多項式時間で解ける問題のクラスは、P で表される。このクラスの問題は、NPクラスに多項式時間チューリング還元で還元可能である。
NP ⊆ P であることは明らかだが、NP、P、NP、P の関係(等価かどうか)は未解決の問題である。詳しくは多項式階層を参照されたい。
A は、クラス A のアルゴリズムに「言語」B のオラクルを付加することで解ける問題のクラスをも意味している。例えば、P は、チューリングマシンに充足可能性問題のオラクルを付与することで多項式時間で解ける問題のクラスである。言語 B がクラス C について完全であるとき、A=A が成り立つ。特に SAT はNP完全問題なので、P=P となる。