我試圖寫一個MATLAB算法，將解決以下問題什麼是我正在尋找的算法的複雜類？
For some symmetric, positive semi-definite matrix S
minimize (over vector x) x'*S*x
subject to sum(x)==n
x(i) is either 1 or 0 for all i
n is an integer < the row/column size of S
我問這個問題here。儘管沒有答案能夠解決問題，但是一些答覆爲我提供了關於我如何自己回答問題的線索。有人向我建議這個問題是NP-Hard，但是因爲我只有CS101對複雜類的理解，所以我很難理解這一點。
我該如何判斷是否是這種情況？如果它是NP-Hard，我應該放棄嘗試尋找解決方案嗎？
有問題的問題是一般二次0-1問題，因此是NP-hard。這個斷言的來源是Pardalos & Jha (1992)。我從this answer得知這篇論文是我提出的一個相關問題。
Pardalos，P.M。，& Jha，S.（1992）。二次0-1編程中唯一性和局部搜索的複雜性。運籌學通訊，11（2），119-123。
NP-Hard是一種說法，即一個問題在多項式時間內無法解決。所以，要放棄這個問題，你必須證明你的問題在多項式時間內是不可解的。 因爲你的約束條件（1）和（3）基本上是相同的，所以我對你的問題公式很困惑。在約束條件（2）中，因爲你想優化它，所以它應該是一個不等式條件，如sum（）< = n。
subject to
0 <= x(i) <= 1 for all i (1)
sum(x)==n (2)
x(i) is either 1 or 0 for all i (3)
如果你想堅持用Matlab，Yalmip是的，你可以考慮的選項之一。
你是對的，對於所有i而言，0 <= x（i）<= 1是多餘的。它不同於'x（i）對於所有i而言是1或0「，但是，因爲後面的代碼清楚地表明值必須是0或1. – user1205197
對於（2），它是正確的爲'=='因爲我沒有試圖優化它。我會預先指定'n'是一些整數。我想盡量減少的是'x'* S * x'。 – user1205197
如果在約束（2）中保留==，那麼在多項式時間內難以解決問題。所以，這個約束需要放寬以便通過使用<=來解決。 –
當parameterized由N，你的問題是W[1]難的，由independent set減少。
那applies even if the entries of S are given在unary。
S = adjacency_matrix +（number_of_vertices - 1）* identity_matrix
通過Gershgorin Circle Theorem，這種矩陣S分別總是積極的半定。
不知道正面的半定義部分是如何影響事物的，但是從NP完全最大集合問題到矩陣必須是對稱的問題版本有一個相當簡單的減少。 – user2357112
請注意，如果它是NP-Hard，您只需*放棄尋找最佳解決方案。有很多方法可以找到好的近似解決方案，即使它們不是最佳解決方案，它們也可能具有實用性。 – Nuclearman