調和奎因 - 麥克羅斯基算法

我看article on wikipdia這個算法，我看到兩個看似矛盾的說法：調和奎因 - 麥克羅斯基算法

「這也給一個確定的方式來檢查布爾函數的最小形式已經達到」

和

‘具有，因爲它解決了這個問題在有限的使用範圍是NP-硬’

想法？

p.s.是否有Visual Studio插件可以通過將此算法應用於突出顯示的代碼來減少條件邏輯？

不要混淆是非確定性的多項式*複雜類*有*算法*即不確定性。兩件完全不同的事情。 – marcog 2011-01-25 23:35:02

該算法需要指數時間。所有NP完全問題都可以在指數時間內解決。據推測，所提到的問題除了是NP難以完成之外還是NP完全的。

的差異可能是因爲你沒有完全瞭解NP難的定義是： http://en.wikipedia.org/wiki/NP-hard

2011-01-25 23:33:19 forefinger

有沒有在這些聲明是矛盾的。
你可能會感到困惑什麼「確定性」是指在這種情況下：

在計算機科學中，確定性的算法是其在非正式方面，可以預見的行爲。給定一個特定的輸入，它將始終產生相同的輸出，並且底層機器將始終通過相同的狀態序列。

在這個意義上說，幾乎所有的廣泛使用CS算法是確定性的。

我相信你已經知道什麼是NP難「是指:)

2011-01-25 23:34:48

回答