In September $1989$, Renegar had this famous sequence of 3 papers titled, "On the Computational Complexity and Geometry of the First-order Theory of the Reals, Part I/II/III". I was wondering if anyone knew of a smaller textbook/course-notes exposition of the at least maybe the main point there.

For example, if I understand correctly, a consequence of all this was an estimate on the running time of solving any polynomial optimization problem (min/maximizing a polynomial with polynomial constraints). If at least this part can be read up from a simpler exposition somewhere else.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.