Prove Symbolic Regression is NP-hard by Symbol Graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913323731124224 |
|---|---|
| author | Song, Jinglu Lu, Qiang Tian, Bozhou Zhang, Jingwen Luo, Jake Wang, Zhiguang |
| author_facet | Song, Jinglu Lu, Qiang Tian, Bozhou Zhang, Jingwen Luo, Jake Wang, Zhiguang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_13820 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Prove Symbolic Regression is NP-hard by Symbol Graph Song, Jinglu Lu, Qiang Tian, Bozhou Zhang, Jingwen Luo, Jake Wang, Zhiguang Computational Complexity Neural and Evolutionary Computing 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. |
| title | Prove Symbolic Regression is NP-hard by Symbol Graph |
| topic | Computational Complexity Neural and Evolutionary Computing |
| url | https://arxiv.org/abs/2404.13820 |