How Hard Is Science?

Symbolic Regression (SR) is the task of finding a closed-form mathematical expression that optimizes some objective. Solving this task is NP-hard. However, SR software routinely discovers accurate, interpretable models without exhaustively searching function space. Motivated by this disconnect between worst-case theory and practical success, we study SR through the lens of \emph{parameterized complexity theory}. In particular, we reanalyze tractability with respect to practically relevant parameters like expression depth, tree size, and number of primitives used. We show that SR is fixed-parameter tractable (FPT) when parameterized by expression depth or tree size, formalizing the tractable regime exploited by bounded-complexity search in popular SR algorithms. However, SR becomes W[1]-hard when parameterized by the number of variables or primitives used, identifying selection as a source of intractability. We further find lower bounds under the exponential time hypothesis, prove approximation hardness, and rule out polynomial kernels for the case where the primitive set is part of the input.

We consider the question of how hard science is by looking at the computational difficulty of the closely related problem of symbolic regression (SR). The idea of SR is to find good equations that fit data, even if one has very little information about what those equations might look like. This is similar to finding good predictive equations in science. It just so happens that classical analysis would say that this is very hard, yet in practice SR is frequently able to find good models. We therefore consider the difficulty of several variations on SR using a non-classical analysis and find that some variations are (in a precise sense of the word) ``easy'' while others remain hard (by any sense of the word). The easy variations tend to look for small equations while the hard ones ask for equations that only use a small number of features. Additionally, depending on the math one chooses to use and the variation of SR, preprocessing the data may or may not make things easier. These results give some intuition for the aspects of science we might hope to automate.