The complexity of deciding consistency of systems of polynomials in exponent inequalities

DOI10.1016/S0747-7171(08)80088-0MaRDI QIDQ1190747zbMATH OpenFDO

Publication date 26 September 1992

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0747-7171(08)80088-0

algebraic complexity decidability exponent polynomials non-standard analysis polynomials in exponent inequalities

Nonstandard models of arithmetic (03H15) Computational aspects and applications of commutative rings (13P99) Real algebraic sets (14P05) Computational aspects in algebraic geometry (14Q99) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Review text

Exponent polynomials are expressions of the form \(P\bigl(e^{h(X_ 1,\dots,X_ n)},X_ 1,\dots,X_ n\bigr)\), where \(P(U,X_ 1,\dots,X_ n)\) and \(h(X_ 1,\ldots,X_ n)\) are polynomials with integer coefficients. Given a system of polynomials in exponent inequalities, the paper presents an algorithm for testing if the system has one solution over the reals \(\mathbb{R}^ n\). Assuming that the degree of all the involving \(P\) and \(h\) polynomials is less than \(d\), that the bit lengths of the integer coefficients are less than \(M\), and that the number of inequalities is less than \(k\), it is reasonable to estimate a bound for the size of the system by \(L=Mkd^ n\) (dense representation). With this notation, the algorithm presented here runs in time polynomial in \(M(nkd)^{n^ 4}\) (i.e. is subexponential in \(L\), as it is bounded by \(L\) to some power which is polynomial in \(\log (L))\). The work extends and uses previous work on the purely algebraic case (systems of polynomial inequalities), in particular requires computation with infinitesimals and some results from non-standard analysis.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: The complexity of deciding consistency of systems of polynomials in exponent inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1190747)