Prove Symbolic Regression is NP-hard by Symbol Graph
Not on the map. Why?
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.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). First posted on arXiv 22 Apr 2024.
Builds on
No reference list yet.
Built on by
Citing papers per year: 2026: 3.
3 papers.
- 2026FePySR: A Neural Feature Extraction Framework for Efficient and Scalable Symbolic Regressioncited by 1
- 2026Certified Learning under Distribution Shift: Sound Verification and Identifiable Structurecited by 0
- 2026Turning Time Series into Algebraic Equations: Symbolic Machine Learning for Interpretable Modeling of Chaotic Time Seriescited by 0
- 2026FePySR: A Neural Feature Extraction Framework for Efficient and Scalable Symbolic Regression12 May 2026
- 2026Turning Time Series into Algebraic Equations: Symbolic Machine Learning for Interpretable Modeling of Chaotic Time Series7 Mar 2026
- 2026Certified Learning under Distribution Shift: Sound Verification and Identifiable Structure6 Feb 2026