対話型証明系
IP の設計者らは Babai の対話型証明系の一般化を意図していたが、逆に制限を加えることを検討した者もいる。その中でも最も価値の高いものとして、PCP(f(n), g(n)) がある。これは MA に制限を加え、Arthur は f(n) 個までのランダムビットだけを利用可能とし、Merlin から送られてくる証拠のうち g(n) ビットだけを調べることができるようにしたものである(調べるビット列の位置は基本的にランダムアクセス)。Sanjeev Arora と Shmul Safra が設計したものであり、PCP の背景には、証明文字列の完全な知識と無作為性のトレードオフを行っても、全体としての能力はあまり低下しないという洞察があった。
PCP クラス群に関していくつかの容易に証明可能な事実がある。PCP(0,poly)(無作為性なし)は、単なる NP である。PCP(poly,0)(証明結果を見ない)は、単なる co-RP である。