Prove Symbolic Regression is NP-hard by Symbol Graph
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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSymbolic RegressionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Evaluating K-Fold Cross Validation for Transformer Based Symbolic Regression Models
Symbolic Regression remains an NP-Hard problem, with extensive research focusing on AI models for this task. Transformer models have shown promise in Symbolic Regression, but performance suffers with smaller datasets. We…
regressionSymbolic RegressionAI Feynman: a Physics-Inspired Method for Symbolic Regression
A core challenge for both physics and artificial intellicence (AI) is symbolic regression: finding a symbolic expression that matches data from an unknown function. Although this problem is likely to be NP-hard in princi…
regressionSymbolic RegressionIdentification of Empirical Constitutive Models for Age-Hardenable Aluminium Alloy and High-Chromium Martensitic Steel Using Symbolic Regression
Process-structure-property relationships are fundamental in materials science and engineering and are key to the development of new and improved materials. Symbolic regression serves as a powerful tool for uncovering mat…
AI Feynman 2.0: Pareto-optimal symbolic regression exploiting graph modularity
We present an improved method for symbolic regression that seeks to fit data to formulas that are Pareto-optimal, in the sense of having the best accuracy for a given complexity. It improves on the previous state-of-the-…
regressionSymbolic RegressionTwo-sample testingSymbolNet: Neural Symbolic Regression with Adaptive Dynamic Pruning for Compression
Compact symbolic expressions have been shown to be more efficient than neural network models in terms of resource consumption and inference speed when implemented on custom hardware such as FPGAs, while maintaining compa…
Jet TaggingModel CompressionregressionSymbolic Regression