We study interactive proofs in the framework of real number complexity as introduced by Blum, Shub, and Smale. The ultimate goal is to give a Shamir like characterization of the real counterpart IP_R of classical IP. Whereas classically Shamir's result implies IP = PSPACE = PAT = PAR, in our framework a major difficulty arises from the fact that in contrast to Turing complexity theory the real number classes PAR_R and PAT_R differ and space resources considered alone are not meaningful. It is not obvious to see whether IP_R is characterized by one of them - and if so by which. In recent work the present authors established an upper bound IP_R is a subset of MA(Exists)R, where MA(Exists)R is a complexity class satisfying PAR_R is a strict subset of MA(Exists)R, which is a subset of PAT_R and conjectured to be different from PAT_R. The goal of the present paper is to complement this result and to prove interesting lower bounds for IP_R. More precisely, we design interactive real protocols for a large class of functions introduced by Koiran and Perifel and denoted by UniformVSPACE^0. As consequence, we show PAR_R is a subset of IP_R, which in particular implies co-NP_R is a subset of IP_R, and P_R^{Res} is a subset of IP_R, where Res denotes certain multivariate Resultant polynomials. Our proof techniques are guided by the question in how far Shamir's classical proof can be used as well in the real number setting. Towards this aim results by Koiran and Perifel on UniformVSPACE^0 are extremely helpful.

In this paper we show that the PCP theorem holds as well in the real number computational model introduced by Blum, Shub, and Smale. More precisely, the real number counterpart NP_R of the classical Turing model class NP can be characterized as NP_R = PCP_R(O(log n), O(1)). Our proof structurally follows the one by Dinur for classical NP. However, a lot of minor and major changes are necessary due to the real numbers as underlying computational structure. The analogue result holds for the complex numbers and NP_C.

The paper surveys some of the author's work studying the algorithmic importance of the tree-width notion in algebraic frameworks. Two approaches are described. The first gives an algorithmicmeta-theoremfor certain logically characterized propertieswithin the Blum-Shub-Smale BSS model of computation over the reals. The second reports on recent joint work with P. Koiran relating Boolean complexity and Valiant's approach to study families of polynomial systems over infinite fields and their complexity. We define particular families of polynomials via bounding the tree-width of suitably attached graphs and study the expressive power of the resulting families. The work described here is partially co-authoredwith and partially verymuch influenced by previous work of Janos A. Makowsky.

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.

This paper deals with complexity classes ${\cal P}_{\Bbb C}$ and ${\cal NP}_{\Bbb C}$ as they were introduced over the complex numbers by Blum, Shub, and Smale [Bull. Amer. Math. Soc., 21 (1989), p. 1]. Under the assumption ${\cal P}_{\Bbb C} \ne {\cal NP}_{\Bbb C}$ the existence of noncomplete problems in ${\cal NP}_{\Bbb C}$ not belonging to ${\cal P}_{\Bbb C}$ is established.

We present a logical approach to complexity over the real numbers with respect to the model of Blum, Shub and Smale. The logics under consideration are interpreted over a special class of two-sorted structures, called R-structures: They consist of a finite structure together with the ordered field of reals and a finite set of functions from the finite structure into R. They are a special case of the metafinite structures introduced recently by Grädel and Gurevich. We argue that R-structures provide the right class of structures to develop a descriptive complexity theory over R. We substantiate this claim by a number of results that relate logical definability on R-structures with complexity of computations of BSS-machines.