How Hard Is Science?

We consider the question of how "hard" science is by looking at the difficulty of turning measurements into empirical law. Historically, this has been done by hand, famously by both Kepler and Planck, but increasingly it has become a target for automated science. Symbolic regression (SR), the task of finding a closed-form mathematical expression that fits data, is the standard formalization of this step. Solving it is known to be NP-hard but, nonetheless, SR software routinely discovers accurate, interpretable models without exhaustively searching function space. Motivated by this disconnect, we study SR through the lens of parameterized complexity theory. We show that SR is fixed-parameter tractable (FPT) when parameterized by expression depth or tree size over a fixed primitive set, matching the tractable regime exploited by bounded-complexity search in popular SR algorithms. In contrast, 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 when the primitive set is part of the input. These results give some intuition for the aspects of science we might hope to automate.