NEXPTIME
NEXPTIME は対話型証明系の話によく登場する。その場合2つの主な特徴がある。まず、MIP証明系は、2つの全能証明機が1つの無作為化多項式時間検証機と通信する(証明機同士は通信しない)。ある文字列が対象言語に含まれる場合、これら証明機は高い確率で検証機を納得させられるはずである。文字列がその言語に含まれない場合、これらの証明機が検証機をだまして納得させられる確率は非常に低い。MIP証明系の一方の証明機だけでは PSPACEの範囲でしか証明できないが、2つの証明機を検証機が相互検証することで NEXPTIME の範囲の証明ができるという点は、非常に興味深い。
もう1つの対話型証明系に関する NEXPTIME の特徴は、それが確率的検査可能証明のクラスの一種であるという点である。NPの定義として、全能証明機がある文字列が言語に含まれることの証明を与えたとき、決定性多項式時間機械がその証明を検証できるクラスであるという定義がある。ここで、この設定に以下の2つの変更を加える。
無作為性を導入し、検証機械がコインを投げて表裏を知ることが可能な機能を持つとする。
検証機にテープの形で証明を与えるのではなく、証明に無作為にアクセスできるようにする。検証機は証明文字列の任意の位置を指定して、対応するビットを受け取る。検証機は多項式長のインデックスを指定できるので、指数関数的に長い証明文字列にインデックスをつけることも可能となる。
これらの拡張により、証明系の能力は格段に強化され、NEXPTIME に属する全言語を認識できるようになる。このクラスをPCPと呼ぶ。