We develop some foundations for a general theory of condition numbers, ill-posed problem instances, and related concepts. Justification for our formalizations is provided by results from semi-algebraic geometry, with particular reliance on the fact that decision methods for the first-order theory of the reals exist, as was proven by Tarski.

This series of papers presents a complete development and complexity analysis of a decision method, and a quantifier elimination method, for the first order theory of the reals. The complexity upper bounds which are established are the best presently available, both for sequential and parallel computation, and both for the bit model of computation and the real number model of computation; except for the bounds pertaining to the sequential decision method in the bit model of computation, all bounds represent significant improvements over previously established bounds.

This series of papers presents a complete development and complexity analysis of a decision method, and a quantifier elimination method, for the first order theory of the reals. The complexity upper bounds which are established are the best presently available, both for sequential and parallel computation, and both for the bit model of computation and the real number model of computation; except for the bounds pertaining to the sequential decision method in the bit model of computation, all bounds represent significant improvements over previously established bounds.

This series of papers presents a complete development and complexity analysis of a decision method, and a quantifier elimination method, for the first order theory of the reals. The complexity upper bounds which are established are the best presently available, both for sequential and parallel computation, and both for the bit model of computation and the real number model of computation; except for the bounds pertaining to the sequential decision method in the bit model of computation, all bounds represent significant improvements over previously established bounds.

Upper bounds on the complexity of approximating solutions of general algebraic formulae over the real numbers are established; included are systems of polynomial equations and inequalities.

Let $d_1 , \cdots ,d_n $ be positive integers. Let $\mathcal{P}$ denote the set of systems of polynomials $f:\mathbb{C}^n \to \mathbb{C}^n $ that have only finitely many zeros, including those “at infinity,” and that satisfy degree $(f_i ) = d_i $ for all i. Let $0 < \varepsilon \leqq R$. It is shown for fixed $d_1 , \cdots ,d_n $, that with respect to a certain model of computation, the worst-case computational complexity of obtaining $\varepsilon $-approximations to at least those zeros $\xi $ satisfying $|\xi | \leqq R$ for arbitrary $f \in \mathcal{P}$ is $\Theta (\log \log (({ R / \varepsilon }))$; that is to say, both upper and lower bounds are proved. An algorithm for proving the upper bound is introduced. The number of operations required by this algorithm is \[O\left[ {n\mathcal{D}^4 (\log \mathcal{D})(\log \log ( { R / \varepsilon } )) + n^2 \mathcal{D}^4 \left( \begin{array}{*{20}c} {1 + \Sigma d_i} \\ n \\ \end{array} \right)^4 } \right],\quad {\text{where }}\mathcal{D} = \prod\limits_{i = 1}^n {d_i .} \]

The decision problem for the existential theory of the reals is the problem of deciding if the set (x in R/sup n/; P(x) is nonempty, where P(x) is a predicate which is a Boolean function of atomic predicates either of which is a Boolean function of atomic predicates either of the form f/sub i/(x)>or=0 or f/sub j/(x)>, the f's being real polynomials. An algorithm is presented for deciding the existential theory of the reals that simultaneously achieves the best known time and space bounds. The time bound for the algorithm is slightly better than any previous bound.>

Let Pd(R) denote the set of degree d complex polynomials with all zeros ζ satisfying |ζ| ≤ R. For d ≥ 2 fixed, we show that with respect to a certain model of computation, the worst-case computational complexity of obtaining an ε-approximation either to one, or to each, zero of arbitrary f ∈ Pd(R) is Θ(log log(R/ε)), that is, we prove both upper and lower bounds. A new algorithm, based on Newton's method, is introduced for proving the upper bound.