Complexity of deciding the first-order theory of real closed fields
1991
Let
denote an ordered field, where δi+1 is infinitesimal relative to the elements of the field ℚi 0 ≤ i < m (by definition, ℚ0=ℚ). Given a formula of the first-order theory of the real closed field ℚm, of the following form:
, where P is a quantifier-free formula containing k atomic subformulas of the form (fj ≥ 0), where
are polynomials such that
, and the absolute value of any integer occurring in the coefficients of the polynomials fj is at most 2M. Let κ=S1+...+Sa denote the number of variables anda ⩽ n the number of quantifiers in the formula. An algorithm is constructed which decides the truth of formulas of the above form in polynomial time with respect to M,
. Previously known algorithms for this problem had complexity of the order of
.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
13
References
2
Citations
NaN
KQI