Is there something like Cook's Theorem for Machine Learning?

Question

Cook's Theorem* says that any problem in NP can be reduced to a SAT problem.

^{*Cook, Stephen A. “The Complexity of Theorem-Proving Procedures.” In Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–58. STOC ’71. New York, NY, USA: Association for Computing Machinery, 1971.}

Is there an analogous theorem for machine learning (ML), stating that all problems in a particular class (e.g., NP) can be solved by ML / neural networks?

^{In physics, I'm reminded of how mechanics equations can be reformulated as a variational problem, i.e., an optimization problem of the Lagrangian (integral of which is a sort of "loss function"). Analogously, perhaps algorithms can be reformulated as a machine learning problem (which is really just an optimization problem, too).}

Answer 1

For neural networks, we have theoretical results like the Universal Approximation Theorem which states that a sufficiently large neural network with certain activation functions can approximate any continuous function on a compact domain. This theorem shows the theoretical expressive power of neural networks, but it doesn’t imply practical solvability or efficient learning within P or NP complexity classes. In fact ML often deals with approximations whose successful "reduction" between problems isn’t well-defined or universally applicable yet, unlike Cook's theorem establishing universal polynomial-time reductions between certain problems.

Probably Approximately Correct (PAC) learning further provides a theoretical framework for understanding which problems are learnable from finite data in theory in polynomial time. The set of PAC-learnable problems is related to complexity classes but doesn't map directly to NP or other standard classes.

An important innovation of the PAC framework is the introduction of computational complexity theory concepts to machine learning. In particular, the learner is expected to find efficient functions (time and space requirements bounded to a polynomial of the example size), and the learner itself must implement an efficient procedure (requiring an example count bounded to a polynomial of the concept size, modified by the approximation and likelihood bounds).