対話型証明系
秘密硬貨は意味がないかもしれないが、確率的検証機械と全能証明機械が多項式回数のやりとりをすることで、クラス IP に属する問題を解くことができる。
クラス IP の能力を示すため、グラフ同型問題を考えてみよう。これはノード数の等しい2つのグラフがあったとき、それらが同じ形であるかを判定する問題である。証明の証拠はノードの対応関係の組合せで示されるので、この問題は NP に属する。もちろん NP は MA に包含されるので、この問題は IP にも属する。また、アディ・シャミアはグラフ同型問題の補問題を解く IP アルゴリズムを発見した。co-NP 問題は NP に属するか不明であり、一般には属さないと考えられている。
そのような機械は NP にあるとは信じられていない多くの問題を解けるだけでなく、一方向性関数が存在することを前提として、検証者に解法についての情報を与えずに多くの問題の解法があるかどうかを決定することができる。