0
$\begingroup$

I am trying to teach P vs NP to some primarily Machine Learning folks. I wanted to come up with an introductory fact to grab their attention.

Reasoning for Question:

  1. Most problems in Machine Learning are NP-hard.

2/3. All NP-Hard problems are the same problem - per reduction unto each-other in trivial poly-time.

Thus, it is the case that most Machine Learning problems are actually just the same problem in a different disguises. Is this true?

Timestamped: https://youtu.be/YX40hbAHx3s?t=406

An estimate on what percent of Machine Learning algorithms are NP-hard would be helpful. For example, regression is not NP-hard, but I was told that the fact that a closed form solution exists for that particular problem is a "miracle". I use the term most loosely. Many will also work.

Improve this question
$\endgroup$
8
  • $\begingroup$ Point (3) is not saying anything and, as written, one can remove 'NP-Complete' from it: 'All problems are the same problem - per reduction unto each other'. The restrictions on how the reduction should be done is the whole point. Point (2) seems to have the two classes swapped. $\endgroup$
    – plop
    Oct 8, 2020 at 19:09
  • $\begingroup$ For your last paragraph, NP-hardness is a property of a problem and not of an algorithm. $\endgroup$
    – Juho
    Oct 8, 2020 at 19:17
  • 3
    $\begingroup$ Much of machine learning is about generalization, which lies beyond the framework of NP-completeness. Also, in practice NP-hard problems vary in difficulty, since the instances are not necessarily worst-case. $\endgroup$
    – Yuval Filmus
    Oct 8, 2020 at 19:19
  • $\begingroup$ @plop Since all NP-Complete problems can be reduced to each other in poly-time, isn't the restriction on how to reduce trivial? $\endgroup$
    – Matthaeus Gaius Caesar
    Oct 8, 2020 at 19:33
  • 1
    $\begingroup$ Beware that NP-Hard $\neq$ NP-Complete. Different NP-Hard problems are not necessarily poly-time reducible to each-other. $\endgroup$
    – Tassle
    Oct 8, 2020 at 20:32

1 Answer 1

Reset to default
1
$\begingroup$

I don't find this a useful or accurate perspective.

It's not true that all NP-hard problems are identical, not even under polynomial-time reductions. All NP-complete problems can be reduced to each other in polynomial time, but NP-complete is different from NP-hard.

When you see someone say something like "all NP-complete problems are the same problem", that is an informal slogan that should not be taken too seriously; you need to look at the technical statement behind that and see whether it is relevant to what you care about. In the context of machine learning, I don't think it's very relevant or useful.

Machine learning is about average-case behavior, not worse-case behavior. NP-hardness is about worst-case behavior.

In machine learning we focus more on behavior on typical problem cases, rather than worst-case problems. For example, the no-free-lunch theorem demonstrates that no ML algorithm will work well on all problems.

In machine learning typically we are more interested in understanding their accuracy rather than their running time, and usually we are concerned with concrete performance on concrete tasks and empirical results rather than asymptotic running time or provable guarantees.

For these reasons, the tools built up for NP-completeness and NP-hardness may not add a lot of insight about machine learning.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Machine learning algorithms are often heuristic solutions to NP-hard problems. Runtime is important. Without these heuristic solutions, most machine learning algorithms would have an average runtime of thousands of years.. $\endgroup$
    – Matthaeus Gaius Caesar
    Oct 9, 2020 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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