NP完全與NP-硬

如果問題已知的是NP完全可以減少到另一個問題乙在多項式時間內，則B是（A）NP完全（B）NP-硬NP完全與NP-硬

沒有給出關於問題B是否在NP中的問題。我很困惑，因爲在Hopcraft和Ullman的書中，如果一個NP完全問題P1在多項式時間內可以歸結爲問題P2，那麼P2就是NP-完全的。但它也需要一個問題是NP-Complete，它應該屬於NP類。夥計們幫助理解這個概念。

來源

2011-11-25 Prashant Bhardwaj

由於有些回答者的注意（有些是*完全*關閉），減少只是讓B NP-Hard，儘管在你的特定情況下，即使沒有明確說明，也許作者認爲它顯然在NP（因此是NPC）。如果它很容易驗證（通常是最簡單的方法屬於NP），那就足夠了。 – davin

如果A可以在多項式時間內減少到B，所有你知道的是B更難然後A.在你的情況下，如果A是NP完全的，B是NP-hard。

如果B也碰巧在NP那麼B將是NP-完全的（因爲NP-完全意味着既在NP中又在NP-中同時）。

但是，沒有什麼能阻止你將A減少到不是NP的問題。例如，它是微不足道的在NP以減少任何問題停機問題 - 也就是除了undecideable到是NP-hard的一個問題：

Construct the following program: 
    Test all possible solutions for A. 
    If one of them is successful halt and otherwise enter an infinite loop. 
A has a solution if-and-only if that program halts

來源

2011-11-25 17:06:02 hugomg

謝謝你的夥計！ –

@Prashant：如果您接受答案來解決問題 – sdcvvc

，那麼您可以接受（綠色標記）此外，upvoting有用的問題和答案永遠不會傷害。 – hugomg

-1

如果A是NP完全的，那麼它也一定是NP。這又意味着可以在多項式時間內驗證A的每個可能的解，這意味着對於B也是如此（因爲A可以在多項式時間內縮減到B）。因此B是NP;它不必被說成是單獨的條件。

來源

2011-11-25 16:42:42 Xion

我的老師告訴我，如果問題Y可以歸結爲問題X，那麼也意味着X至少和Y一樣硬，因爲如果你可以解決X，你就可以解決Y. 我也在引用維基百科在這裏「一個問題H是NP難的當且僅當存在一個NP完全問題L是多項式時間Turing可歸約爲H.」 –

A可簡化爲B意味着B的任何解都可以用來求解A.這並不是對B的複雜性的上限，所以B可能比NP更難。 –

-1正如大衛布朗所說 – sdcvvc

由於問題A可以在多項式時間內簡化爲問題B，因此問題B的任何解都可以用來找到A的解。或者更簡單地說，求解A不會比求解B困難。因爲我們知道A是NP-complete，哪類問題至少與NP完全問題一樣困難？

僅供參考，您可能還想看看關於NP-Hard（特別是第二句），NP-Complete的維基百科文章。和Reduction。

來源

2011-11-25 17:00:37

這就是我所問的，爲什麼B不僅僅是NP-hard。 B可能比NP更難。這樣B應該是NP-hard。如果它也在NP中，那麼我們可以說B是NP完全的。 –

是的，B是NP-Hard。 NP-Hard問題「至少與NP中最難的問題一樣困難」。由於A可以簡化爲B，B至少與A一樣硬，並且由於A是NP完全的，所以它是NP中最難的問題之一。 –

謝謝@David。我終於明白了。在閱讀了許多不同來源後，我有點困惑。 –

回答

相關問題