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.

Let k be a field. The author continues the work of Lickteig [SIAM J. Comput., 16 (1987), pp. 278–311 ] and extends it in two directions: (1) A lower bound on the Ostrowski complexity of division in a finite extension field $A \supset k:L_{{\text{DIV}}} \geqq 3[A:k] + \log _2 [B:k] - 2$, where $B \subset A$ is some simple extension of k of maximal degree. The proof combines the technique of adjoining intermediate results to the ground field [T. Lickteig, op, cit.] and lower bound criteria for approximative complexity recently obtained by Griesser [Theoret. Comput. Sci., 46 (1986), pp. 329–338]. (2) An optimal lower bound for the complexity of inversion in a quadratic alternative algebra A of dimension greater than or equal to $2,A \ne k \times k:L_{{\text{INV}}} = 2\dim A - {\text{index of the norm}}$.

We show that, for any quadratic field extension $k \subset K$, the division in K requires exactly six essential multiplications and divisions over k. In particular, complex division in real arithmetic requires six multiplications and divisions. If additions and subtractions are counted as well, exactly nine operations are required if $k \subset K$ is a radical extension; otherwise ten operations are required.