任何NP到SAT。如何做到這一點，並證明這是可能的？

Question

讓我們從這裏開始： 據說所有NP問題可以減少到SAT（布爾可滿足性問題）。爲了更準確地到電路SAT，因爲像NP這樣的所有決策問題應該以回答是或否。

但是現在，如果我有一個隨機的NP問題，如何建立一個布爾電路來測試，如何分組我的輸入，什麼樣的門（AND，NOT或OR等）應該連接這些輸入。所以基本上，我的問題如何設計布爾電路它給出了一個答案TRUE或FALSE。

最後，那個答案意味着什麼。我明白TRUE，因爲這個NP問題可以在多項式時間和FALSE中解決，我是否正確？

這在我心中是一團糟，如果我在解釋我的問題時發生邏輯錯誤，不要太離譜:)我希望你能理解它。

激動地等待答案。

Answer 1

我明白混亂，但你的理解並不完全如此。

NP-硬度是決策問題的限定條件，即答案的問題是是或否。如果我們想要證明決策問題是NP難題，我們通過將至少作爲難點這樣做是一個我們知道它已經是NP難題的問題，例如SAT。

我們如何證明問題A至少與問題B一樣困難？那麼，我們可以短語作爲

，如果我們能夠解決，我們也可以解決乙

因此，給予實例問題B的，我們把它轉換爲問題的一個實例，使用我們的解決方案來解決它，並將其轉換回B的解決方案。假設兩個對話都很容易，我們知道A不會比B更容易，因爲A 的解決方案也是解決方案B 。

---

因此你的理解使它倒退了。爲了證明某些問題是NP難題，我們要證明它至少與SAT一樣困難，即給定SAT的任意實例，將其轉換爲問題的實例，然後解決該問題。如果答案是「是」，那麼原來的SAT問題是可以滿足的，否則就不是。

---

現在，正如我在評論中所寫，沒有標準的方法來進行轉換。您不知何故需要操縱您的問題，以便它「看起來像SAT」，以便進行轉換。對於一些其他問題更容易的問題，但我認爲這是NP硬度證明中最難的部分。

人們通常會做的是他們正在尋找另一個已知是NP-hard的問題，但看起來更像是他們自己的問題。這樣，減少變得更容易一些。但仍然需要大量的工作和創造力。我建議你看看一些現有的證據，看看別人如何做到這一點。