The complexity of deciding consistency of systems of polynomials in exponent inequalities (Q1190747)

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.