問題の

解法を見つけることは難しいが、

その解法を見て正しいかどうかを検証することは簡単な性質

定義

アルゴリズムVに対して、言語Aを次のように定義できる時、VをAの検証装置という

A=\{w|Vはある文字列cに対して\lang w,c\rangを受理\}

検証装置の計算時間はwの長さに関してのみ測る。よって多項式時間検証装置とは、wの長さに対して多項式時間でcの検証を行うアルゴリズムである。言語Aが多項式時間検証装置を持つ時、Aを多項式検証可能という

cは、Aの要素であることの「証明書」とか「証明」とかと呼ばれる

多項式検証可能性のある問題の例

ハミルトン路問題 ref p.316

ある数が合成数かどうかを判定する問題

これを判定するのは難しいが、因数を見せられれば積がその数になることを確かめればよいだけなので検証は容易

RSA暗号とかそんな感じってことだよな

直感的には、どんな問題も持つ性質じゃね？って感じがするがそんなことはない

例えばハミルトン閉路問題の補問題を考える

問. 与えられたグラフGはハミルトン閉路を持たないか？

どうにかして、「ハミルトン閉路は持たない」と結論が出たとしても、それを検証するのは容易ではない

参考