# Symbolic Regression is NP-hard

arXiv: https://arxiv.org/abs/2207.01018 · HTML: https://mlsanity.com/paper/2207.01018/

## Key facts

- Cited by 71 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 62 references that are in the map.
- First posted on arXiv 3 Jul 2022.

## Builds on (most cited first, 22 of 22)

- [AI Feynman: a Physics-Inspired Method for Symbolic Regression](https://mlsanity.com/paper/1905.11481/) (2019)
- [Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradients](https://mlsanity.com/paper/1912.04871/) (2019)
- [Contemporary Symbolic Regression Methods and their Relative Performance](https://mlsanity.com/paper/2107.14351/) (2021)
- [End-to-end symbolic regression with transformers](https://mlsanity.com/paper/2204.10532/) (2022)
- [Optimal Sparse Decision Trees](https://mlsanity.com/paper/1904.12847/) (2019)
- [Rediscovering orbital mechanics with machine learning](https://mlsanity.com/paper/2202.02306/) (2022)
- [Symbolic Physics Learner: Discovering governing equations via Monte Carlo tree search](https://mlsanity.com/paper/2205.13134/) (2022)
- [SymFormer: End-to-end symbolic regression using transformer-based architecture](https://mlsanity.com/paper/2205.15764/) (2022)
- [Deep Symbolic Regression for Recurrent Sequences](https://mlsanity.com/paper/2201.04600/) (2022)
- [Interpretable Policies for Reinforcement Learning by Genetic Programming](https://mlsanity.com/paper/1712.04170/) (2017)
- [Rethinking Symbolic Regression Datasets and Benchmarks for Scientific Discovery](https://mlsanity.com/paper/2206.10540/) (2022)
- [Learning concise representations for regression by evolving networks of trees](https://mlsanity.com/paper/1807.00981/) (2018)
- [Fast, accurate, and transferable many-body interatomic potentials by symbolic regression](https://mlsanity.com/paper/1904.01095/) (2019)
- [A Greedy Search Tree Heuristic for Symbolic Regression](https://mlsanity.com/paper/1801.01807/) (2018)
- [Symbolic Regression by Exhaustive Search: Reducing the Search Space Using Syntactical Constraints and Efficient Semantic Structure Deduplication](https://mlsanity.com/paper/2109.13895/) (2021)
- [On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networks](https://mlsanity.com/paper/1704.02958/) (2017)
- [Learning a Formula of Interpretability to Learn Interpretable Formulas](https://mlsanity.com/paper/2004.11170/) (2020)
- [Model Learning with Personalized Interpretability Estimation (ML-PIE)](https://mlsanity.com/paper/2104.06060/) (2021)
- [Constructing Parsimonious Analytic Models for Dynamic Systems via Symbolic Regression](https://mlsanity.com/paper/1903.11483/) (2019)
- [Predicting Friction System Performance with Symbolic Regression and Genetic Programming with Factor Variables](https://mlsanity.com/paper/2107.09484/) (2021)
- [CoNSoLe: Convex Neural Symbolic Learning](https://mlsanity.com/paper/2206.00257/) (2022)
- [Symbolic Regression for Space Applications: Differentiable Cartesian Genetic Programming Powered by Multi-objective Memetic Algorithms](https://mlsanity.com/paper/2206.06213/) (2022)

## Built on by (most cited first, 30 of 71)

- [LLM-SR: Scientific Equation Discovery via Programming with Large Language Models](https://mlsanity.com/paper/2404.18400/) (2024)
- [Interpretable Scientific Discovery with Symbolic Regression: A Review](https://mlsanity.com/paper/2211.10873/) (2022)
- [Transformer-based Planning for Symbolic Regression](https://mlsanity.com/paper/2303.06833/) (2023)
- [Poisoning Attacks on LLMs Require a Near-constant Number of Poison Samples](https://mlsanity.com/paper/2510.07192/) (2025)
- [LLM-SRBench: A New Benchmark for Scientific Equation Discovery with Large Language Models](https://mlsanity.com/paper/2504.10415/) (2025)
- [Interpretable Machine Learning for Science with PySR and SymbolicRegression.jl](https://mlsanity.com/paper/2305.01582/) (2023)
- [Deep Generative Symbolic Regression with Monte-Carlo-Tree-Search](https://mlsanity.com/paper/2302.11223/) (2023)
- [Pruner-Zero: Evolving Symbolic Pruning Metric from scratch for Large Language Models](https://mlsanity.com/paper/2406.02924/) (2024)
- [A computational framework for physics-informed symbolic regression with straightforward integration of domain knowledge](https://mlsanity.com/paper/2209.06257/) (2022)
- [AI-Aristotle: A Physics-Informed framework for Systems Biology Gray-Box Identification](https://mlsanity.com/paper/2310.01433/) (2023)
- [Symbolic Regression via Control Variable Genetic Programming](https://mlsanity.com/paper/2306.08057/) (2023)
- [Symbolic Regression for PDEs using Pruned Differentiable Programs](https://mlsanity.com/paper/2303.07009/) (2023)
- [SymbolNet: Neural Symbolic Regression with Adaptive Dynamic Pruning for Compression](https://mlsanity.com/paper/2401.09949/) (2024)
- [Mimicking the Physicist's Eye:A VLM-centric Approach for Physics Formula Discovery](https://mlsanity.com/paper/2508.17380/) (2025)
- [Interpretable Symbolic Regression for Data Science: Analysis of the 2022 Competition](https://mlsanity.com/paper/2304.01117/) (2023)
- [MESSY Estimation: Maximum-Entropy based Stochastic and Symbolic densitY Estimation](https://mlsanity.com/paper/2306.04120/) (2023)
- [GFN-SR: Symbolic Regression with Generative Flow Networks](https://mlsanity.com/paper/2312.00396/) (2023)
- [Vertical Symbolic Regression via Deep Policy Gradient](https://mlsanity.com/paper/2402.00254/) (2024)
- [Improving Monte Carlo Tree Search for Symbolic Regression](https://mlsanity.com/paper/2509.15929/) (2025)
- [Improving Genetic Programming for Symbolic Regression with Equality Graphs](https://mlsanity.com/paper/2501.17848/) (2025)
- [Racing Control Variable Genetic Programming for Symbolic Regression](https://mlsanity.com/paper/2309.07934/) (2023)
- [Learning Interpretable Network Dynamics via Universal Neural Symbolic Regression](https://mlsanity.com/paper/2411.06833/) (2024)
- [Large Language Models for Extrapolative Modeling of Manufacturing Processes](https://mlsanity.com/paper/2502.12185/) (2025)
- [Physics-Grounded Motion Forecasting via Equation Discovery for Trajectory-Guided Image-to-Video Generation](https://mlsanity.com/paper/2507.06830/) (2025)
- [What can we Learn by Predicting Accuracy?](https://mlsanity.com/paper/2208.01358/) (2022)
- [No One-Size-Fits-All Neurons: Task-based Neurons for Artificial Neural Networks](https://mlsanity.com/paper/2405.02369/) (2024)
- [Constrained or Unconstrained? Neural-Network-Based Equation Discovery from Data](https://mlsanity.com/paper/2406.02581/) (2024)
- [Ab Initio Nonparametric Variable Selection for Scalable Symbolic Regression with Large p](https://mlsanity.com/paper/2410.13681/) (2024)
- [Deep Symbolic Optimization: Reinforcement Learning for Symbolic Mathematics](https://mlsanity.com/paper/2505.10762/) (2025)
- [Analyzing Generalization in Pre-Trained Symbolic Regression](https://mlsanity.com/paper/2509.19849/) (2025)

## Abstract (arXiv)

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.