The complexity of deciding consistency of systems of polynomials in exponent inequalities
type: Item
instance of: scholarly article
title: The complexity of deciding consistency of systems of polynomials in exponent inequalities
zbMATH Open document ID: 0784.68046
DOI: 10.1016/S0747-7171(08)80088-0
author: Nicolai Vorobjov
published in: Journal of Symbolic Computation
publication date: 1992-09-26T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 14Q99
Mathematics Subject Classification ID: 14P05
Mathematics Subject Classification ID: 03H15
Mathematics Subject Classification ID: 13P99
zbMATH DE Number: 56192
zbMATH Keywords: algebraic complexity
zbMATH Keywords: decidability
zbMATH Keywords: exponent polynomials
zbMATH Keywords: polynomials in exponent inequalities
zbMATH Keywords: non-standard analysis
reviewed by: Tomas Recio
MaRDI profile type: Publication
cites work: The complexity of elementary algebra and geometry
cites work: Q4057338
cites work: Q3728104
cites work: Q5187264
cites work: Q4079605
cites work: Q4132530
cites work: Complexity of deciding Tarski algebra
cites work: Solving systems of polynomial inequalities in subexponential time
cites work: Q4143433
cites work: Integer Arithmetic Algorithms for Polynomial Real Zero Determination
cites work: Q3686991
cites work: Differential Topology
cites work: Q5588717
cites work: On the Betti Numbers of Real Varieties
cites work: Q4771357
cites work: Q5807665
cites work: Q4189745
cites work: Q3336589
cites work: Q3973352
cites work: Q4168680
cites work: Q4137157
Recommended article: Q3973352
Recommended article: Deciding consistency of systems of exponential-polynomial inequalities in subexponential time
Recommended article: Q3485804
Recommended article: On the complexity exponent of polynomial system solving
Recommended article: Complexity of the resolution of parametric systems of polynomial equations and inequations
Recommended article: An improvement of the complexity bound for solving systems of polynomial equations
Recommended article: Q4242506
Recommended article: On the complexity of solving a bivariate polynomial system
Recommended article: Solving systems of polynomial inequalities in subexponential time
Recommended article: Complexity of solving parametric polynomial systems
description: scientific article; zbMATH DE number 56192