共NPがNPのサブセットでない理由

Question

誰かが私にこの質問をしてくれました。大学の教科書を読んでいても、私はそれに答えることができませんでした。具体的には、ここでは共同NPの定義は、多くの教科書である：Aがあれば共同NPにあり、多項式時間手続きVがある場合のみ

定義1

「問題（・、・）結合した多項式P（）は、x∈Aの場合にのみ∀y場合、そのような：| Y |≤のP（| X |）、V（x、y）は1"

1. これはありません= Aが共NPであれば証明書を持たなければならない（すべてのyは証明書なので）、したがってAもNPにあるということを意味するか？

2. いくつかの考えでは、私は上記の定義が正しいとは確信していません。

定義2

「AがあればNPにあり、多項式時間 手続きV（・、・）と多項式時間バインドがある場合にのみ、決定問題：NPの次の定義を考えます| y |≦p（| x |）∧V（x、y）= 1 "となるようなp∈Pである。

定義3

"決定問題Aは、∀y：| y |が成り立つ場合に限り、x∈Aとなるような多項式時間結合p（）が存在する場合に限り、共NPになる。 V（x、y）= 1となるような多項式時間手順V（x、y）= 1が存在しないので、定義3は定義1と等価ではない。

Answer 1

これは、Aが共NPであれば、証明書を持つ必要があります（すべてのyは証明書であるため）したがって、AもまたNPにあるか？

No. NPは、NPの定義の意味で問題Aの検証者ではない。その意味での検証者であるためには、検証者でなければならない。 x∈A bを求めるV（x、y）= 1となるような単一のyを見つける。このVを使って、yのすべての可能な値を調べる必要がある。

提案されている共NPの「直接的な定義」は間違っています。問題Aについては、引数を無視して直ちに1を返す手続きであるVを選ぶことができます。したがって、定義によって、共NPに問題はありません。