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.

Improve this question
$\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$
    – Gerry Myerson
    Commented 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$
    – Noah Schweber
    Commented 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...
    Commented Apr 2, 2014 at 2:28
  • 3
    $\begingroup$ Computing the tensor rank is also NP-hard. $\endgroup$
    – Federico Poloni
    Commented 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$
    – Jérémy Blanc
    Commented Apr 2, 2014 at 9:40

4 Answers 4

Reset to default
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)

Improve this answer
$\endgroup$
1
  • $\begingroup$ Very good. Thank you very much for your help. $\endgroup$
    – x.y.z...
    Commented 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What do you mean by 'computing spectral norm is easy'? Are there any known deterministic approximation algorithms? $\endgroup$
    – mirewine
    Commented Sep 21, 2022 at 13:27
  • $\begingroup$ Spectral norm of a matrix is just its largest singular value. $\endgroup$
    – Nathaniel Johnston
    Commented Sep 21, 2022 at 15:04
  • $\begingroup$ Do you by chance have a reference for the NP-hardness of deciding positivity of a linear map? Or is this something that's "likely true" given its connection with the separability problem? $\endgroup$
    – Frederik vom Ende
    Commented Nov 13 at 11:12
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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Can you add some references, please? $\endgroup$
    – Felix Goldberg
    Commented Apr 2, 2014 at 11:18
  • $\begingroup$ References added. $\endgroup$
    – Lior Silberman
    Commented Apr 3, 2014 at 5:38
4
$\begingroup$

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

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .