您好，我很難理解P，NP和多項式時間減少的主題。 我試圖在網上搜索它，並問我的一些朋友，但我還沒有得到任何好的答案。NP中的語言（問題）與語言（問題）之間的多項式時間縮減P
我想問一個一般性的問題關於這個話題：
設A，B是語言（或一組問題）的對 讓C，D是NP 語言的下一個的都一定是真的（可以大於1）
在此先感謝您的回答。
（1）爲真（用B={}和B={all words}除外），用下面的多項式還原：
Let w_t be some word such that B(w_t)=true, and w_f be some word such that B(w_f)=false.
Given a word w: Run A(w). If A(w)=true, return w_t - otherwise, return w_f
以上是多項式的減少，因爲所有operartions是多項式和減少收率的輸出B(f(w))=true當且僅當。 （2）再次如此，同樣的減少（同樣，如果你可以假設有一個w_t和一個w_f如上所述）。
（3）這是錯誤的，假設P！= NP。
假設存在這樣的減少，並且讓它成爲f:Sigma*->Sigma*。
檢查問題C=SAT和A一些問題P，並讓M_A是解決A.
我們將展示我們可以在多項式時間內解決SAT（但由於我們假設P！= NP多項式算法，它是不可能的 - 矛盾，所以f不存在）。
給定SAT w的一個實例，運行w'=f(w)。運行M_A（w'），並回答相同的問題。
以上顯然是多項式，它總是返回正確答案 - 從多項式約化的定義 - f(w)在A當且僅當w在C。
因此 - 上述算法在多項式時間內解決SAT問題 - 矛盾。 （4）也是錯誤的，因爲案例（3）被包含在其中。