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