We exhibit a condition-based analysis of the adaptive subdivision algorithm due to Plantinga and Vegter. The first complexity analysis of the \pv~Algorithm is due to Burr, Gao and Tsigaridas who proved a \mathcalO \big(2^τ d^4 łog d \big) worst-case cost bound for degree d plane curves with maximum coefficient bit-size~τ. This exponential bound, it was observed, is in stark contrast with the good performance of the algorithm in practice. More in line with this performance, we show that, with respect to a broad family of measures, the expected time complexity of the \pv~Algorithm is bounded by O(d^7) for real, degree d, plane curves. We also exhibit a smoothed analysis of the \pv~Algorithm that yields similar complexity estimates. To obtain these results we combine robust probabilistic techniques coming from geometric functional analysis with condition numbers and the continuous amortization paradigm introduced by Burr, Krahmer and Yap. We hope this will motivate a fruitful exchange of ideas between the different approaches to numerical computation.

We describe and analyze an algorithm for computing the homology (Betti numbers and torsion coefficients) of basic semialgebraic sets that works in weak exponential time. That is, of a set of exponentially small measure in the space of data, the cost of the algorithm is exponential in the size of the data. All algorithms previously proposed for this problem have a complexity that is doubly exponential (and this is so for almost all data).

The 17th of the problems proposed by Steve Smale for the 21st century asks for the existence of a deterministic algorithm computing an approximate solution of a system of n complex polynomials in $n$ unknowns in time polynomial, on the average, in the size N of the input system. A partial solution to this problem was given by Carlos Beltran and Luis Miguel Pardo who exhibited a randomized algorithm, call it LV, doing so. In this paper we further extend this result in several directions. Firstly, we perform a smoothed analysis (in the sense of Spielman and Teng) of algorithm LV and prove that its smoothed complexity is polynomial in the input size and σ-1, where σ controls the size of the random perturbation of the input systems. Secondly, we perform a condition-based analysis of LV. That is, we give a bound, for each system f, of the expected running time of LV with input f. In addition to its dependence on N this bound also depends on the condition of f. Thirdly, and to conclude, we return to Smale's 17th problem as originally formulated for deterministic algorithms. We exhibit such an algorithm and show that its average complexity is NO(log log N). This is nearly a solution to Smale's 17th problem.

We provide several machine-independent characterizations of deterministic complexity classes in the model of computation proposed by L. Blum, M. Shub and S. Smale. We provide a characterization of partial recursive functions over any arbitrary structure. We show that polynomial time over an arbitrary structure can be characterized in terms of safe recursion. We show that polynomial parallel time over an arbitrary structure can be characterized in terms of safe recursion with substitutions.

We define counting classes #PR and #PC in the Blum-Shub-Smale setting of computations over the real or complex numbers, respectively. The problems of counting the number of solutions of systems of polynomial inequalities over R, or of systems of polynomial equalities over C, respectively, turn out to be natural complete problems in these classes. We investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over R) and algebraic sets (over C). We prove that the problem to compute the (modified) Euler characteristic of semialgebraic sets is FPR#P RR-complete, and that the problem to compute the geometric degree of complex algebraic sets is FPR#PCC-complete. We also define new counting complexity classes GCR and GCC in the classical Turing model via taking Boolean parts of the classes above, and show that the problems to compute the Euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. We complement the results in the Turing model by proving, for all k ∈ N, the FPSPACE-hardness of the problem of computing the kth Betti number of the set of real zeros of a given integer polynomial. This holds with respect to the singular homology as well as for the Borel-Moore homology.

We define a counting class ${\rm #P}_\add$ in the Blum--Shub--Smale setting of additive computations over the reals. Structural properties of this class are studied, including a characterization in terms of the classical counting class $#{\sf P}$ introduced by Valiant. We also establish transfer theorems for both directions between the real additive and the discrete setting. Then we characterize in terms of completeness results the complexity of computing basic topological invariants of semilinear sets given by additive circuits. It turns out that the computation of the Euler characteristic is ${\rm FP}_{\rm add}^{{\rm #P}_{\rm add}}$-complete, while for fixed k the computation of the kth Betti number is ${\rm FPAR}_{\rm add}$-complete. Thus the latter is more difficult under standard complexity theoretic assumptions. We use all of the above to prove some analogous completeness results in the classical setting.

In this paper we prove that, in the context of weak machines over $\Bbb R$, there are no sparse $\NP$-hard sets.

During the last few decades two traditions of computing have grown and grown further apart.

This paper has two agendas. One is to develop the foundations of round-off in computation. The other is to describe an algorithm for deciding feasibility for polynomial systems of equations and inequalities together with its complexity analysis and its round-off properties. Each role reinforces the other.

Abstract In this paper we deal with the logical description of complexity classes arising in the real number model of computation introduced by Blum, Shub, and Smale [4]. We adapt the approach of descriptive complexity theory for this model developped in [14] and extend it to capture some further complexity classes over the reals by logical means. Among the latter we find NCℝ, PARℝ, EXPℝ and some others more.

In this paper, we study the computational power of real Turing machines over binary inputs. Our main result is that the class of binarysets that can be decided by real Turing machines in parallel polynomial time is exactly the class PSPACE/poly.

In this paper we consider real counterparts of classical probabilistic complexity classes in the framework of real Turing machines as introduced by Blum, Shub, and Smale [2].We give an extension of the well-known "BPP ~P/poly" result from discrete complexity theory to a very general setting in the real number model.This result holds for real inputs, real outputs, and random elements drawn from an arbitrary probability distribution over lR~.Then we turn to the study of Boolean parts, that is, classes of languages of zero-one vectors accepted by real machines.In particular we show that the classes BPP, PP, PH, and PSPACE are not enlarged by allowing the use of real constants and arithmetic at unit cost provided we restrict branching to equality tests.

The aim of this paper is to survey certain theoretical aspects of the complexity of quantifier elimination in the elementary theory of the real numbers with real constants, and to present some new results on the subject. We use the new model of computation introduced by L. Blum, M. Shub and S. Smale that accepts as inputs vectors of real numbers and allows the transfer of the structural approach to computability and complexity for computations with real numbers. More concretely, we give a proof of the existence of NPR-complete problems. Also, we introduce a new complexity class PATR which describes the complexity of the decision of quantified formulae and, in order to study its relationship with the already existing complexity classes, a model for parallel computations is also introduced. Using the classes resulting by bounding resources in this parallel model, some separation results are finally obtained. In particular, we show that the polynomial hierarchy overs the reals is strictly contained in PATR.

An usual classification of undecidable problems in computability theory is the one given by the arithmetical hierarchy introduced by Kleene. Very recently. L. Blum, M. Shub and S. Smale devised a model of computation able to work with real numbers and showed the main properties of a computability theory for that model. In this paper we introduce the arithmetical hierarchy for it. A syntactical characterization is given, together with some complete problems. Also, it is shown that if nondeterministic machines are considered instead of deterministic ones, a different set of classes is obtained (unlike the classical case) and all these classes are related with the classification of sets of reals done in descriptive set theory.