多項式還原是否可逆？

Question

是這種說法真的還是假的：「如果一個問題的是多項式歸結爲一個問題B，那麼B題也必須多項式簡化爲」。

Answer 1

這是不對的，考慮還原爲關係爲其硬度小於或等於。例如，如果A可以多項式還原爲B，則意味着硬度（需要計算的計算量）就A而言。如果A可簡化爲B，則意味着A比B簡單（或與B一樣），這意味着如果可以解決B，那麼也可以解答A.

一些補充信息： P中的任何問題都是簡單的，可以在多項式時間內解決的問題，可以歸結爲NP完全問題（例如SAT）中的任何問題。這意味着P中的問題比NP中的問題更簡單。現在，如果你的陳述是真的，那麼NP-complete中的問題將在多項式時間內解決，這似乎是不可能的（沒有人證明或反駁它）。如果有人解決它會有混亂！

https://en.wikipedia.org/wiki/P_versus_NP_problem

SAT problem

A world with P=NP

Answer 2

下面是從複雜性理論（C.H. PAPADIMITRIOU，計算複雜性）一個非常著名的畢業文本（稍微編輯）圖示。它顯示了從一個到乙的降低。

從甲到乙的減少是解決，它由一個翻譯- [R那的甲每個實例映射到B的一個實例的的算法，以及B的算法。翻譯必須確保答案甲（X）和乙（- [R（X））是相同的。

了這樣的轉換的存在並不能保證逆翻譯也存在。直觀的甲實例的圖像可能形成乙的容易實例的一個子集。

任何人都可以很容易地提出問題的簡單的例子，其中減少的一個方向並不能保證在其他方向上的縮小。例如，2-SAT可簡化爲SAT，但2-SAT可用多項式時間求解，而SAT則是NP-complete。

Answer 3

這是錯誤的。考慮以下問題：

給定有限自動機，它是否停止給定輸入？

由於所有確定性有限自動機停在所有輸入上，所以對這個問題的答案始終是肯定的。但是，這個問題是多項式時間可以減少到以下問題：

給定一個圖靈機，它是否停止給定的輸入？

對於這個問題的答案恰好在一般情況下是不可判定的。這是暫停問題。但是，如果我們對這個問題的甲骨文，我們當然可以用它來回答第一個問題，雖然更高效：

1. 生產圖靈機等同於DFA
2. 使用Oracle，以確定是否圖靈機暫停。

然而，圖靈機的暫停問題並非多項式時間減少到DFA的暫停問題。