爲什麼共NP不是NP的子集

Question

有人問我這個問題，我發現即使花了一些時間重新閱讀我的大學教科書後我也無法回答。具體而言，這裏是許多課本共NP的定義：

定義1

「中的一個問題是在共同NP當且僅當有一個多項式時間過程V（·，·）和多項式粘結的p（），使得x∈A當且僅當∀y：| Y |≤p（| X |），V（X，Y）= 1"

1. 不此意味着如果A在NP中，那麼它必須有一個證書（因爲每個Y都將是一個證書），因此A也在NP中？

2. 有些想法，我不確定上述定義是否正確。注射了NP的以下定義：

定義2

「的決定問題的是在NP，當且僅當存在一個多項式時間 過程V（·，·）和多項式時間界（x，y）= 1時，p（）使得x∈A當且僅當| y |≤p（| x |）∧V（x，y）= 1「

co-NP的直接定義似乎是：

定義3

「決策問題A是共NP當且僅當存在多項式時間界p（）使得x∈A當且僅當∀y：| y | （x，y）= 1時，存在不存在多項式時間過程V（。，。）的情況。但是，定義3與定義1不等價，因爲V我是否缺少任何東西？謝謝！

Answer 1

這不是說如果A在NP-NP中，那麼它必須有一個證書（因爲每個Y都是一個證書）因此，A也是NP？

號V是不是問題的NP中的定義意義上的驗證。當V是在這個意義上驗證器，我們需要能夠以確定x∈Ab y找到一個單一的y使得V（x，y）= 1。有了這個V，我們需要檢查所有可能的y值。

你提出的co-NP的「直接定義」是錯誤的。對於任何問題A，我們可以選擇V作爲忽略它的參數並立即返回1的過程。因此，根據你的定義，在共同NP中沒有問題。