{"id":"arxiv/2601.21917","url":"https://arxiv.org/abs/2601.21917","tags":["math.OC","cs.CC","cs.LG","math.NA","stat.ML"],"score":0,"title":"On Approximate Computation of Critical Points","domain":"math.OC","source":"arxiv","authors":["Amir Ali Ahmadi","Georgina Hall"],"reviews":0,"subject":"math.OC","summary":"We show that computing even very coarse approximations of critical points is intractable for simple classes of nonconvex functions. More concretely, we prove that if there exists a polynomial-time algorithm that takes as input a polynomial in $n$ variables of constant degree (as low as three) and outputs a point whose gradient has Euclidean norm at most $2^n$ whenever the polynomial has a critical point, then P=NP. The algorithm is permitted to return an arbitrary point when no critical point exists. We also prove hardness results for approximate computation of critical points under…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-01-29","reactions":{}}