REVIEW 9 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
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 9 Pith papers
-
LLM-Based Scientific Equation Discovery via Physics-Informed Token-Regularized Policy Optimization
PiT-PO adaptively fine-tunes an LLM during symbolic regression search using physics-validity and token-level redundancy constraints, reporting state-of-the-art benchmark results and a periodic-hill turbulence closure.
-
MOT-SR: Multi-Objective Tool-Augmented Scientific Equation Discovery with Large Language Models
MOT-SR combines tool-augmented data analysis with multi-objective Pareto selection to discover symbolic equations, outperforming LLM-based and classical SR baselines on benchmarks and an EMRI orbital-correction task.
-
Symbolic Regression for Shared Expressions: Introducing Partial Parameter Sharing
Introduces partially-shared parameters for symbolic regression with multiple categorical variables, matching prior fit quality on a supernovae dataset with fewer parameters.
-
Fast Symbolic Regression Benchmarking
A curated-list plus early-termination protocol for symbolic regression benchmarks raises measured rediscovery rates and cuts benchmark compute by roughly half.
-
$\mathcal{CP}$-Analyses with Symbolic Regression
Symbolic regression produces analytic, detector-level CP-odd observables for WBF Higgs production and an analytic reconstruction of the Collins-Soper angle in ttH that are competitive with black-box ML and classical methods.
-
Advancing network resilience theories with symbolized reinforcement learning
A self-inductive pipeline (reinforcement learning plus symbolic regression) yields the formula d·s (degree × steady state) for identifying keystone nodes in networks with heterogeneous dynamics, along with refinements...
-
SymMatika: Structure-Aware Symbolic Discovery
A structure-aware symbolic regression framework combining multi-island genetic programming with reusable motif libraries reports state-of-the-art recovery rates on Nguyen and Feynman benchmarks, including 61% on Nguyen-12.
-
Modeling the Optical Properties of Biological Structures using Symbolic Regression
Symbolic regression retrieves closed-form refractive index expressions, including Cauchy-like models, from reflectance spectra of aragonite multilayers and a jewel beetle elytron.
-
ECSEL: Explainable Classification via Signomial Equation Learning
ECSEL fits signomial equations (sums of power-law terms) as interpretable classifiers, recovering signomial regression targets faster than general-purpose symbolic regression and matching black-box accuracy on several...
Discussion (0). Sign in to comment.