title: What's the complexity class of the algorithm I'm seeking?
body: <p>I'm trying to write a MATLAB algorithm that will resolve the following problem</p>
  
  <pre><code>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 &lt; the row/column size of S
  </code></pre>
  
  <p>I'd asked about this question <a href="https://stackoverflow.com/questions/33738857/matlab-find-abbreviated-version-of-matrix-that-minimises-sum-of-matrix-elements">here</a>. Although no answer there satisfies the problem, some of the responses provide me with leads as to how I might answer the question myself. It's been suggested to me that this problem is NP-Hard, but because I have only a CS101 understanding of complexity classes I'm having trouble understanding this.</p>
  
  <p>How can I tell whether this is the case? If it is NP-Hard, should I just give up on trying to find a solution?</p>