Optimization and NP_R-Completeness of Certain Fewnomials Institutional Repository Document

abstract

• We give a high precision polynomial-time approximation scheme for the supremum of any honest n-variate (n+2)-nomial with a constant term, allowing real exponents as well as real coefficients. Our complexity bounds count field operations and inequality checks, and are polynomial in n and the logarithm of a certain condition number. For the special case of polynomials (i.e., integer exponents), the log of our condition number is quadratic in the sparse encoding. The best previous complexity bounds were exponential in the sparse encoding, even for n fixed. Along the way, we extend the theory of A-discriminants to real exponents and certain exponential sums, and find new and natural NP_R-complete problems.

authors

• Rojas, Joseph

author list (cited authors)

• Pebay, P., Rojas, J. M., & Thompson, D. C.

complete list of authors

• Pebay, Philippe||Rojas, J Maurice||Thompson, David C

Book Title

• arXiv

publication date

• April 2009

keywords

• 49 Mathematical Sciences
• 4901 Applied Mathematics
• 4903 Numerical And Computational Mathematics
• 4904 Pure Mathematics

Digital Object Identifier (DOI)

• 10.48550/arxiv.0904.4060