基於NP驗證者的定義

我是一名計算機科學專業的學生，我在理解基於驗證者的NP問題定義時遇到了一些問題。基於NP驗證者的定義

的定義說，一個問題是NP如果能夠在polinomial時間確定性圖靈機，給出了「證書」驗證。

但會發生什麼，如果證書正是問題的解決方案？這只是一點點，它在輸入規模上顯然受到多項式限制，並且顯然可以在恆定的，因此是多項式時間中進行驗證。

因此，每個決策問題都屬於NP。

我在哪裏錯了？

2011-07-04 Simone

但會發生什麼，如果證書正是問題的解決方案？這只是一點點，它在輸入規模上顯然受到多項式限制，並且顯然可以在恆定的，因此是多項式時間中進行驗證。

爲什麼「明明」？您可能需要花費指數的時間來驗證解決方案，在這種情況下，問題不一定在NP中。重點是，即使證書是一個決策問題的單個位，您不知道該位應該是零還是一個來解決問題。（如果你總是沒有知道，然後在P或NP中任何決策問題是在固定時間內可解。）

2011-07-04 18:15:24

我的意思是：給定問題，如果我使用輸出作爲證書，如果問題得到驗證，則爲1，如果問題未驗證，則爲0。因此，驗證機器只需將證書作爲輸出返回給出正確答案。我的疑惑不在於對np類的概念理解，而在於對形式化的理解。 – Simone

@Simone：我認爲你的證書定義錯了。 [Wikipedia]（http://en.wikipedia.org/wiki/NP_%28complexity%29）將* certificate *（隱含地）定義爲待驗證的候選解決方案，不一定是單個位。 –

不一定，但它可以是1個單一位。如果該位是問題的輸出，那麼它可以用作驗證者的輸出 – Simone

並非所有的問題都可以在多項式時間內驗證，即使該解決方案是在長度多項式。讓我們考慮旅行推銷員問題。給出一個解決方案，你只能驗證給定的解決方案是否是城市之旅，但是你不能分辨是否是最短長度的遊覽，除非你探索所有可能的遊覽。

因此，在大多數情況下的決策問題是NP完全的（例如，爲了找到一組城市是否包含旅遊），而優化問題是NP難的（例如發現的最小長度遊）

2011-07-04 18:17:14 Akhil

回答