Polynomial-time approximate-root conjecture for circuit-system Gale duals
Polynomial-time approximate-root conjecture for circuit-system Gale duals
Let ), let and for all , and consider the univariate rational function
For coprime integers , define the logarithmic height of by , with . Set and . An approximate root is understood in the sense of Smale.
Polynomial-time approximate-root conjecture. Following this notation, one can find approximate roots for all the real roots of in time polynomial in .
This conjecture concerns the real-solving complexity of circuit systems, which generalize univariate trinomial equations. It is motivated by reductions of circuit-system solving to real roots of Gale-dual rational functions; its status is not resolved in the supplied text.
Sources & referencesView supporting material
Primary source
Emma Boniface, Weixun Deng and J. Maurice Rojas, “Trinomials and Deterministic Complexity Limits for Real Solving”, arXiv:2202.06115 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.