8
$\begingroup$

I am curious about NP-hard problems in linear algebra and real analysis. An example in linear algebra would be the calculation of the permanent.

I would thus like to collect in this thread a list of problems specifically in real analysis and linear algebra which are proven to be NP-hard. References to articles or books on this subject would also be helpful.

Any help will be greatly appreciated.

$\endgroup$
6
  • 7
    $\begingroup$ The Bible is Garey and Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. There is a long list of NP-complete problems, gathered by subject area. $\endgroup$ Apr 1, 2014 at 22:55
  • 8
    $\begingroup$ I'm not sure in what sense the Riemann hypothesis is a "problem" here; "problem" in complexity theory means a set of (things coded by) natural numbers. $\endgroup$ Apr 1, 2014 at 23:43
  • $\begingroup$ Riemann hypothesis is a conjecture that one must prove or disprove. That's what I meant to say by problem. Thanks for your comments. $\endgroup$
    – x.y.z...
    Apr 2, 2014 at 2:28
  • 3
    $\begingroup$ Computing the tensor rank is also NP-hard. $\endgroup$ Apr 2, 2014 at 6:39
  • 7
    $\begingroup$ Proving a conjecture is maybe a hard thing, but has nothing to do with the word "hard" of "NP-hard", as Noah S explained. Hence, talking about Riemann hypothesis in this context is quite weird. $\endgroup$ Apr 2, 2014 at 9:40

4 Answers 4

6
$\begingroup$

Here is one such result.

Stephen A. Vavasis. "On the complexity of nonnegative matrix factorization." 2007. (arXiv abstract link)

"In this report, we define an exact version of NMF [nonnegative matrix factorization]. Then we establish several results about exact NMF: (1) that it is equivalent to a problem in polyhedral combinatorics; (2) that it is NP-hard; and (3) that a polynomial-time local search heuristic exists."

There is now quite a bit known about this important problem, e.g.,

Arora, Sanjeev, et al. "Computing a nonnegative matrix factorization--provably." Proceedings of the 44th Symposium on Theory of Computing. ACM, 2012. (ACM link)

Incidentally, NMF played a role in the Netflix Prize problem:

Gábor Takács, et al. Matrix factorization and neighbor based algorithms for the Netflix prize problem. In: Proceedings of the 2008 ACM Conference on Recommender Systems, Lausanne, Switzerland, 267-274, 2008. (ACM link)

$\endgroup$
1
  • $\begingroup$ Very good. Thank you very much for your help. $\endgroup$
    – x.y.z...
    Apr 2, 2014 at 2:33
9
$\begingroup$

The tensor product has a way of making easy problems into (NP-)hard problems. Rank of a 2-tensor (matrix)? Easy. Rank of a 3-tensor? NP-hard. Spectral norm of a matrix? Easy. Spectral norm of a 3-tensor? NP-hard. Etc. There is a nice article by Hillar and Lim about this.

As a direct corollary of the above fact, many natural linear algebra problems that come up in quantum information theory are NP-hard:

  • Determining whether or not a quantum state is entangled

  • Computing pretty much any entanglement monotone (squashed entanglement, entanglement cost, relative entropy of entanglement, and so on)

  • Holevo capacity of a quantum channel

  • Minimum entropy of a quantum channel

  • Plenty of other problems are even "harder" than NP-hard (see this survey article)

These problems can sometimes be rephrased in a way that doesn't use the tensor product at all even. For example, the problem of determining whether or not a linear map is positive is NP-hard. That is, given a linear map $\Phi$ that sends matrices to matrices, determine whether or not $\Phi(X)$ is positive semidefinite whenever $X$ is positive semidefinite.

$\endgroup$
2
  • $\begingroup$ What do you mean by 'computing spectral norm is easy'? Are there any known deterministic approximation algorithms? $\endgroup$ Sep 21, 2022 at 13:27
  • $\begingroup$ Spectral norm of a matrix is just its largest singular value. $\endgroup$ Sep 21, 2022 at 15:04
5
$\begingroup$

You may want to look at the work of Arora, Barak, Ragavendra, Steurer etc relating details of graph spectra to expansion of small sets and to the Unique Games Conjecture. Sample references are:

Ragavendra–Steurer, Ragavendra–Steurer–Tetali,Arora–Barak–Steurer.

$\endgroup$
2
  • 2
    $\begingroup$ Can you add some references, please? $\endgroup$ Apr 2, 2014 at 11:18
  • $\begingroup$ References added. $\endgroup$ Apr 3, 2014 at 5:38
4
$\begingroup$

Given a symmetric matrix do determine it whether it is copositive is NP-Hard.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.