# Prove Symbolic Regression is NP-hard by Symbol Graph

arXiv: https://arxiv.org/abs/2404.13820 · HTML: https://mlsanity.com/paper/2404.13820/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2024.

## Built on by (most cited first, 3 of 3)

- [FePySR: A Neural Feature Extraction Framework for Efficient and Scalable Symbolic Regression](https://mlsanity.com/paper/2605.12704/) (2026)
- [Certified Learning under Distribution Shift: Sound Verification and Identifiable Structure](https://mlsanity.com/paper/2602.17699/) (2026)
- [Turning Time Series into Algebraic Equations: Symbolic Machine Learning for Interpretable Modeling of Chaotic Time Series](https://mlsanity.com/paper/2603.07261/) (2026)

## Abstract (arXiv)

Symbolic regression (SR) is the task of discovering a symbolic expression that fits a given data set from the space of mathematical expressions. Despite the abundance of research surrounding the SR problem, there's a scarcity of works that confirm its NP-hard nature. Therefore, this paper introduces the concept of a symbol graph as a comprehensive representation of the entire mathematical expression space, effectively illustrating the NP-hard characteristics of the SR problem. Leveraging the symbol graph, we establish a connection between the SR problem and the task of identifying an optimally fitted degree-constrained Steiner Arborescence (DCSAP). The complexity of DCSAP, which is proven to be NP-hard, directly implies the NP-hard nature of the SR problem.