REVIEW 6 cited by
Symbolic Regression is NP-hard
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Symbolic Regression is NP-hard
read the original abstract
Symbolic regression (SR) is the task of learning a model of data in the form of a mathematical expression. By their nature, SR models have the potential to be accurate and human-interpretable at the same time. Unfortunately, finding such models, i.e., performing SR, appears to be a computationally intensive task. Historically, SR has been tackled with heuristics such as greedy or genetic algorithms and, while some works have hinted at the possible hardness of SR, no proof has yet been given that SR is, in fact, NP-hard. This begs the question: Is there an exact polynomial-time algorithm to compute SR models? We provide evidence suggesting that the answer is probably negative by showing that SR is NP-hard.
Forward citations
Cited by 6 Pith papers
-
FunctionEvolve: Structure-Guided Symbolic Regression with LLMs
FunctionEvolve recovers 107 exact symbolic forms out of 129 synthetic tasks (82.9% SA@50) by using expression-tree structure for evolutionary search, parent selection, mutation, and coefficient scoring with LLMs.
-
Learning dynamical systems with biochemically informed neural ordinary differential equations
BINODEs combine known stoichiometric matrices with neural network processes to learn and recover dynamics in biochemical systems while incorporating biological constraints.
-
The finite expression method for turbulent dynamics with high-order moment recovery
A two-stage symbolic regression plus generative model framework recovers governing interaction terms and forcing in stochastic triad models while accurately predicting statistical moments up to order five.
-
CMBolic: Symbolic emulators for the Cosmic Microwave Background. I. Lensing
CMBolic supplies analytic emulators for CMB lensing spectra achieving 0.27-0.32% mean fractional error, validated against CLASS on ACT DR6 and Planck lensing data.
-
Discovery of Nonlinear Dynamics with Automated Basis Function Generation
AutoSINDy automatically builds a tailored basis library from PySR symbolic regression and applies SINDy to recover ground-truth nonlinear dynamics with 92.8% success under noise.
-
Neuro-Symbolic AI for Analytical Solutions of Differential Equations
SIGS is a neuro-symbolic framework that discovers analytical solutions to PDEs by generating grammar-constrained expressions, embedding them in a topology-regularised latent manifold, and refining structure and coeffi...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.