Q

如何演示NP-complete

2014-01-07 65 views -4 likes

-4

如何證明下一個問題是NP-complete。給定一個矩陣A和b一個向量，找到一個滿足不等式Ax≤b的非負整數向量x。如何演示NP-complete

2014-01-07 user3170921

+1

這不是主題，因爲這樣的演示不是編程，但我不能說在StackExchange的計算機科學站點歡迎它，因爲它沒有顯示任何功能。 –

A

回答

0

最簡單的方式演示NP-compleate是創建算法，它將解決問題（找到向量x），然後估計它的複雜性。

2014-01-07 21:55:25 arheops

+1

展示一種算法來解決問題永遠不足以證明問題是NP完全的，因爲問題的NP完全性是解決問題的所有**算法的一個屬性。 –

+0

這是不正確的，因爲這樣你就會證明這個問題是NP。爲了證明這是NP完全的，你還需要將這個問題簡化爲一個NP完全問題，如（SAT，3SAT等）。 – user3170921

相關問題