The complexity of deciding consistency of systems of polynomials in exponent inequalities
- Vorobjov, Nikolaj N.
Publication date
February 1992
DOI Publisher
Published by Elsevier Ltd. ISSN
0747-7171Abstract
AbstractSuppose the polynomials P1…, Pk∈ℤ[X1,…,Xn, U], h∈ℤ[X1,…,Xn] have degrees deg(Pi), deg(h)<d and the absolute value of any coefficient of Pi or h is less or equal to 2M for all 1≤i≤k. An algorithm is described which recognizes the consistency in ℝn of the system of inequalities P1(X1,...Xn, eh(X1,…,Xn))≥0,…,Pk(X1,…,Xn, eh(X1,…,Xn)≥0 within time polynomial in M(nkd)n4
Add to ORKG