L を言語、P を計算機、V を多項式時間計算機とする。

対話 (P,V) が

• Completeness - 任意の x∈L に対し、(P,V)(x) は、x のビット長に関して 1/2 + non negligible な確率で accept される
• Soundness - L に属さない任意の x、および任意の計算機 P^* に対し、(P^*,V)(x) は、x のビット長に関して 1/2 + non negligible な確率で reject される

を満たすとき、(P,V) は L に関する所属の対話証明あるいは単に証明と言い、P を証明者、V を検証者と言う。

L がPSPACEに属する言語であれば L に関する所属の対話証明が存在し、そしてその逆も言える事が知られている。