多項式検証可能性
polynomial verifiability
問題の
解法を見つけることは難しいが、
その解法を見て正しいかどうかを検証することは簡単な性質
定義
アルゴリズム$ Vに対して、言語$ Aを次のように定義できる時、$ Vを$ Aの検証装置という
$ A=\{w|Vはある文字列$ cに対して$ \lang w,c\rangを受理$ \}
検証装置の計算時間は$ wの長さに関してのみ測る。よって多項式時間検証装置とは、$ wの長さに対して多項式時間で$ cの検証を行うアルゴリズムである。言語$ Aが多項式時間検証装置を持つ時、$ Aを多項式検証可能という
$ cは、$ Aの要素であることの「証明書」とか「証明」とかと呼ばれる
多項式検証可能性のある問題の例
これを判定するのは難しいが、因数を見せられれば積がその数になることを確かめればよいだけなので検証は容易
RSA暗号とかそんな感じってことだよなmrsekut.icon 直感的には、どんな問題も持つ性質じゃね？って感じがするがそんなことはない
問. 与えられたグラフ$ Gはハミルトン閉路を持たないか？
どうにかして、「ハミルトン閉路は持たない」と結論が出たとしても、それを検証するのは容易ではない
参考