我正在寻找的算法的复杂度 class 是多少？

Question

我正在尝试编写一个 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

我问过这个问题。尽管那里没有答案可以解决问题，但一些回答为我提供了线索，让我知道我该如何自己回答这个问题。有人向我建议这个问题是 NP-Hard，但因为我对复杂性只有 CS101 理解类我很难理解这个问题。

如何判断是否属于这种情况？如果它是 NP-Hard，我是否应该放弃尝试寻找解决方案？

Answer 1

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 是您可以考虑的选项之一。

Answer 2

问题是一个一般的二次0-1问题，因此是NP难的。此断言的来源是 Pardalos & Jha (1992). I learned of this paper from 我提出的相关问题。

Pardalos, P.M., & Jha, S. (1992)。二次 0–1 规划中唯一性和局部搜索的复杂性。运筹学快报，11(2)，119-123。

Answer 3

当parameterized by n, your problem is W[1]-hard, by reduction from independent set。
那applies even if the entries of S are given in unary.

S = adjacency_matrix + ( number_of_vertices - 1 ) * identity_matrix

根据Gershgorin Circle Theorem，这样的矩阵S总是半正定的。

我正在寻找的算法的复杂度 class 是多少？

What's the complexity class of the algorithm I'm seeking?

algorithm

complexity-theory