我正在學習NP-Completeness，我對NP問題的定義有疑問。NP中的非確定性是什麼？
材料說
不確定性指的是一個解決方案可以在O（1）時間猜測出來的多項式多種選擇
在這裏，這是什麼由polynomially many options in O(1) time是什麼意思？
例如，在着名的3SAT問題的情況下，是不是有成倍多的選擇？
（B.C.每個文字可以是true或false，如果有n個文字，選項總數是2*2*2* ... * 2 = 2^n）
然而，它說3SAT問題是NP難題。即使存在指數多的證書，它怎麼會成爲NP問題呢？
感謝
這個報價似乎是措辭它的一個奇怪的方式，但它可能指的是類似的東西能夠挑選爲O 1和N之間的隨機數（1） - 有n個可能性，但只挑一個需要O（1）。還有：nondeterministic algorithms。 「非確定性多項式時間」是NP的完整定義 - 「多項式時間」非常重要 - 您做出的每個決策都可能採用O（1），但是存在多項式多項決策，導致理論上可以解決的問題在多項式時間內，如果您可以在每個步驟做出正確的選擇或同時執行所有選項。
拍攝高度爲p（n）的k-tree樹。如果您從根目錄的每個步驟（隨機）選取正確的子項，或者您可以以某種方式同時訪問所有路徑，則可以在O（p（n））中找到正確的葉子。當然，在實踐中，你不能依靠做出正確的隨機選擇，也不能擁有無限多的處理器 - 如果你要順序地訪問所有節點，那將需要O（k p（n） ）。
對於3SAT，我們可以隨機挑選真或假的每一個文字，這使我們如果我們所有的隨機選擇是正確的將產生正確的結果多項式算法。
如果你已經有**解決方案，你可以證明它在多項式時間是正確的。 **找到**多項式時間的解是P的含義。 – Dukeling
我知道這是NP的一部分。我很好奇的是上面的報價。 「一種解決方案可以在O（1）時間的多項式多項式中被猜出來」是什麼意思？ – kong0329
如果引用是正確的，那麼它就不是在談論猜測整個NP問題的解決方案 - 這可以從線性或多項式時間的指數多數解中猜測出來。相反，它會談論你可以在O（1）「步驟」中做出多大的猜測。即使那麼這是一個有點狡猾 –