NP-Complete證明減少（方向）？

Question

爲什麼你不得不減少的NP完全的算法，你要證明該算法是NP完全問題，而不是反之亦然？我覺得解釋很簡單 - 我已經在網上搜索了它，但沒有成功 - 但我的想法並沒有很好地包圍它。

謝謝:)

Answer 1

因爲如果你能問題的減少問題B，那麼問題B不能低於A.任何容易，畢竟，你現在有解決問題的一個實例的新方式！把它變成問題B的一個實例並解決這個問題。如果B很容易，那麼在這個過程中A也很容易。

，只有當翻譯問題實例的過程本身並不難，這就是爲什麼你還必須證明工作。如果翻譯被允許很難，它可以解決這個問題，讓B變得微不足道。

而且本身只證明題B NP難的，爲了證明問題B是NP完全問題也必須證明它在NP（通常是更容易比減少）。

其他的方式只是表明你的問題並不比NP完全問題，這也不是完全沒用的困難，但一般不太感興趣。例如，你就可以解決問題「是存在的整數x使得x*3=9」與使用二進制乘法和編碼的電路，作爲一個實例SAT，但問題是容易得多一個SAT解算器。