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 Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-01-29 Page: https://delphi.science/r/arxiv/2601.21917 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…