mlsanityData to 7 Oct 2026

Symbolic Regression is NP-hard

arXiv 2207.01018 ↗First posted 3 Jul 2022cs.NE cs.AIcited by 68

Not on the map. Why?

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.

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

Builds on

22 of 62 references.

References · 22

  1. 2019AI Feynman: a Physics-Inspired Method for Symbolic Regressioncited by 536
  2. 2019Deep symbolic regression: Recovering mathematical expressions from data via risk-seeking policy gradientscited by 294
  3. 2021Contemporary Symbolic Regression Methods and their Relative Performancecited by 209
  4. 2022End-to-end symbolic regression with transformerscited by 195
  5. 2019Optimal Sparse Decision Treescited by 104
  6. 2022Rediscovering orbital mechanics with machine learningcited by 71
  7. 2022Symbolic Physics Learner: Discovering governing equations via Monte Carlo tree searchcited by 61
  8. 2022SymFormer: End-to-end symbolic regression using transformer-based architecturecited by 56
  9. 2022Deep Symbolic Regression for Recurrent Sequencescited by 53
  10. 2017Interpretable Policies for Reinforcement Learning by Genetic Programmingcited by 47
  11. 2022Rethinking Symbolic Regression Datasets and Benchmarks for Scientific Discoverycited by 44
  12. 2018Learning concise representations for regression by evolving networks of treescited by 33
10 more
  1. 2019Fast, accurate, and transferable many-body interatomic potentials by symbolic regressioncited by 23
  2. 2018A Greedy Search Tree Heuristic for Symbolic Regressioncited by 17
  3. 2021Symbolic Regression by Exhaustive Search: Reducing the Search Space Using Syntactical Constraints and Efficient Semantic Structure Deduplicationcited by 17
  4. 2017On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel Methods and Neural Networkscited by 16
  5. 2020Learning a Formula of Interpretability to Learn Interpretable Formulascited by 14
  6. 2021Model Learning with Personalized Interpretability Estimation (ML-PIE)cited by 9
  7. 2021Predicting Friction System Performance with Symbolic Regression and Genetic Programming with Factor Variablescited by 7
  8. 2022CoNSoLe: Convex Neural Symbolic Learningcited by 7
  9. 2019Constructing Parsimonious Analytic Models for Dynamic Systems via Symbolic Regressioncited by 6
  10. 2022Symbolic Regression for Space Applications: Differentiable Cartesian Genetic Programming Powered by Multi-objective Memetic Algorithmscited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 14; 2024: 17; 2025: 22; 2026: 12.

68 papers.

Sort:

By area:

  1. 2024LLM-SR: Scientific Equation Discovery via Programming with Large Language Modelscited by 117
  2. 2022Interpretable Scientific Discovery with Symbolic Regression: A Reviewcited by 105
  3. 2023Transformer-based Planning for Symbolic Regressioncited by 72
  4. 2025Poisoning Attacks on LLMs Require a Near-constant Number of Poison Samplescited by 66
  5. 2025LLM-SRBench: A New Benchmark for Scientific Equation Discovery with Large Language Modelscited by 61
  6. 2023Deep Generative Symbolic Regression with Monte-Carlo-Tree-Searchcited by 40
  7. 2024Pruner-Zero: Evolving Symbolic Pruning Metric from scratch for Large Language Modelscited by 40
  8. 2023Interpretable Machine Learning for Science with PySR and SymbolicRegression.jlcited by 36
  9. 2022A computational framework for physics-informed symbolic regression with straightforward integration of domain knowledgecited by 31
  10. 2023AI-Aristotle: A Physics-Informed framework for Systems Biology Gray-Box Identificationcited by 29
  11. 2023Symbolic Regression via Control Variable Genetic Programmingcited by 8
  12. 2023Symbolic Regression for PDEs using Pruned Differentiable Programscited by 6
38 more
  1. 2023Interpretable Symbolic Regression for Data Science: Analysis of the 2022 Competitioncited by 6
  2. 2024SymbolNet: Neural Symbolic Regression with Adaptive Dynamic Pruning for Compressioncited by 6
  3. 2024Vertical Symbolic Regression via Deep Policy Gradientcited by 6
  4. 2025Mimicking the Physicist's Eye:A VLM-centric Approach for Physics Formula Discoverycited by 6
  5. 2025Improving Monte Carlo Tree Search for Symbolic Regressioncited by 6
  6. 2023MESSY Estimation: Maximum-Entropy based Stochastic and Symbolic densitY Estimationcited by 5
  7. 2023GFN-SR: Symbolic Regression with Generative Flow Networkscited by 5
  8. 2025Improving Genetic Programming for Symbolic Regression with Equality Graphscited by 5
  9. 2023Racing Control Variable Genetic Programming for Symbolic Regressioncited by 4
  10. 2024Learning Interpretable Network Dynamics via Universal Neural Symbolic Regressioncited by 4
  11. 2025Large Language Models for Extrapolative Modeling of Manufacturing Processescited by 4
  12. 2025Physics-Grounded Motion Forecasting via Equation Discovery for Trajectory-Guided Image-to-Video Generationcited by 4
  13. 2022What can we Learn by Predicting Accuracy?cited by 3
  14. 2024No One-Size-Fits-All Neurons: Task-based Neurons for Artificial Neural Networkscited by 3
  15. 2024Constrained or Unconstrained? Neural-Network-Based Equation Discovery from Datacited by 3
  16. 2024Ab Initio Nonparametric Variable Selection for Scalable Symbolic Regression with Large pcited by 3
  17. 2025Deep Symbolic Optimization: Reinforcement Learning for Symbolic Mathematicscited by 3
  18. 2026Data-driven discovery of governing differential equations across physical systemscited by 3
  19. 2024Inexact Simplification of Symbolic Regression Expressions with Locality-sensitive Hashingcited by 2
  20. 2024ISR: Invertible Symbolic Regressioncited by 2
  21. 2024Shape Constraints in Symbolic Regression using Penalized Least Squarescited by 2
  22. 2024Neural Symbolic Regression of Complex Network Dynamicscited by 2
  23. 2025Discovering equations from data: symbolic regression in dynamical systemscited by 2
  24. 2025Data-driven Discovery of Digital Twins in Biomedical Researchcited by 2
  25. 2025Analyzing Generalization in Pre-Trained Symbolic Regressioncited by 2
  26. 2025EGG-SR: Embedding Symbolic Equivalence into Symbolic Regression via Equality Graphcited by 2
  27. 2023Stretched and measured neural predictions of complex network dynamicscited by 1
  28. 2023Information Fusion via Symbolic Regression: A Tutorial in the Context of Human Healthcited by 1
  29. 2023Physical Symbolic Optimizationcited by 1
  30. 2023Vertical Symbolic Regressioncited by 1
  31. 2024Interactive Symbolic Regression through Offline Reinforcement Learning: A Co-Design Frameworkcited by 1
  32. 2024A Functional Analysis Approach to Symbolic Regressioncited by 1
  33. 2024Shape Arithmetic Expressions: Advancing Scientific Discovery Beyond Closed-Form Equationscited by 1
  34. 2024A Personalised Learning Tool for Physics Undergraduate Students Built On a Large Language Model for Symbolic Regressioncited by 1
  35. 2024Enhancing Symbolic Regression and Universal Physics-Informed Neural Networks with Dimensional Analysiscited by 1
  36. 2025Neuro-Symbolic AI for Analytical Solutions of Differential Equationscited by 1
  37. 2025Graph-Eq: Discovering Mathematical Equations using Graph Generative Modelscited by 1
  38. 2025Interpretable Non-linear Survival Analysis with Evolutionary Symbolic Regressioncited by 1

50 most cited of 68 All 68 (JSON)