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:
- 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?
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.