我們如何知道NP完全問題是NP中最難的？

2

正如其他人已經正確地表明，問題的存在是NP，但不是NP完全意味着P！= NP，所以找到一個會帶給你一個永恆的榮耀。一個被認爲屬於這一類的着名問題是integer factorization。然而，你原來的問題是

不能存在於NP，我們可能尚未發現或證明問題存在，但無法減少到任何NP完全問題？

答案是no。根據NP完備性的定義，問題A爲NP完全的兩個必要條件之一是每個NP問題都需要在多項式時間內可縮減爲A.如果您想了解如何證明每個NP問題可以在多項式時間到一些NP-完全問題時減少，看看Cook-Levin theorem的證明表明3-SAT問題是NP-完全的。這是第一個被證實的NP完全問題，其他許多NP完全問題後來被證明是NP完全的，從3-SAT到這些問題找到適當的減少。

來源

2016-06-01 07:52:25

+0

謝謝！ SAT理念使其完全合情合理。 – rb612

+0

@ rb612歡迎您！ –

1

NP由所有能夠（理論上）通過能夠做出幸運猜測，猜測解決方案並檢查多項式時間解決方案是正確的問題來解決的所有問題。例如，旅行商問題「我可以訪問美國所有50個州的首都，行程少於9,825英里」可以通過猜測旅行並檢查它不太長而解決。

NP中的一個問題是基本上模擬一個帶有各種輸入的可編程計算機電路，並檢查是否可以實現某個輸出。而且這種可編程計算機電路足夠強大，可以解決NP中的所有問題。

所以是的，我們知道所有關於NP的所有問題。（那麼當然NP完全問題可以用定義來解決NP中的任何問題，如果有問題解決不了，這個問題不在NP中）。

來源

2016-05-31 19:59:57 gnasher729

+0

感謝您的回答。那麼，爲什麼不可能找到NP中的算法X，並且NP完全問題不能簡化爲X？ – rb612

+0

@ rb612如果在NP中存在問題X但不是NP-Complete，那麼NP-Complete是NP的一個真子集。但是，P不能等於NP，因爲P中的每個問題都可以用P的多項式時間來約簡，所以如果P = NP，NP中的所有問題都必須是NP-Complete（即NP和多項式時間可以減少到彼此）。 – Patrick87

1

除了我們如何知道我們已經發現NP中的每個問題？

我們沒有。宇宙中所有問題的集合不僅是無限的，而且是不可數的。

難道不存在我們可能沒有發現的問題，或者證明存在於NP中，但不能簡化爲任何np-complete問題嗎？

我們不知道。我們懷疑是這種情況，但這尚未得到證實。如果我們找到一個不是NP完全的NP問題，這將證明P =/= NP。

這是CS中未解決的重大問題之一。許多出色的思想家一直在採取措施，但這個堅果一直是一個棘手的問題。

來源

2016-05-31 20:13:52

+0

太有意思了。你能否解釋一點關於找到一個NP不完全的NP問題對P =/= NP來說必然是證明？因爲我認爲證明P =/= NP的唯一方法是證明沒有任何算法能夠在確定性多項式時間內解決NP完全問題。 – rb612

+0

@ rb612如果在NP中存在問題X但不是NP-Complete，那麼NP-Complete是NP的一個真子集。但是，P不能等於NP，因爲P中的每個問題都可以用P的多項式時間來約簡，所以如果P = NP，NP中的所有問題都必須是NP-Complete（即NP和多項式時間可以減少到彼此）。 – Patrick87

+0

@ Patrick87謝謝！然而，接受的答案是NP中的所有問題都可以歸結爲NP完全問題。那麼它已經被證明已經或者還是未知數？你能詳細說明你的意思嗎？「那麼P不能等於NP，因爲P中的每個問題都是多項式時間可減少到P中的所有其他問題。我沒有看到P中每個問題彼此減少如果NP⊂NP-complete，P≠NP。 – rb612

我們如何知道NP完全問題是NP中最難的？

回答

相關問題