Deciding consistency of systems of exponential-polynomial inequalities in subexponential time
1992
Let the polynomials P1...,Pk∃ Z[u,X1...,Xn], h ∃ Z[X1,...,Xn] have degrees
,
and assume that absolute values of any coefficients of Pi and h is less than or equal to 2M for all l ≤ i ≤ k. The article present an algorithm to recognize the consistency in Rn of the system of inequalities
, in time polynomial in\((nkd)^{n^4 } \). This result is a generalization of the subexponential-time algorithms of [4, 5, 23] for deciding consistency of systems of polynomial inequalities, and can be considered a contribution to the solution of Tarski's decidability problem concerning the first order theory of reals with exponentiation [1].
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
0
Citations
NaN
KQI