2022/07/03 by Marco Virgolin, Virgolin, Marco, Solon P. Pissis +1 · 16 citations
Computer Science · #Artificial Intelligence (cs.AI) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Machine Learning and Data Classification #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · pdf · doi:10.48550/arxiv.2207.01018
openalex publication_date 2022/07/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.