1. Prove Symbolic Regression is NP-hard by Symbol Graph
- Author
-
Song, Jinglu, Lu, Qiang, Tian, Bozhou, Zhang, Jingwen, Luo, Jake, and Wang, Zhiguang
- Subjects
Computer Science - Computational Complexity ,Computer Science - Neural and Evolutionary Computing - Abstract
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.
- Published
- 2024