Two \(P\)-complete problems in the theory of the reals (Q1203649): Difference between revisions

We propose the parallel real RAM as a model for defining a class of problems dealing with real numbers that are decidable in fast parallel time. This formulation avoids uniformity considerations and the resulting class is trivially included in \(P\). We use reductions in this class (in fact, using constant parallel time) to give our main result, the existence of \(P\)-complete problems for the real model. Two problems with this property are exhibited: the evaluation of algebraic circuits that have sign gates, and the solution of systems of equalities and inequalities via substitutions. A very recent result shows that in the real case, we have indeed \(P\neq NC\) [see \textit{F. Cucker}, J. Complexity 8(3), 230-238 (1992)]. As a consequence, the problems above cannot be solved by parallel algorithms running in polylogarithmic time. These results are a first step toward [\textit{L. Blum}, \textit{M. Shub} and \textit{S. Smale}, Bull. Am. Math. Soc. 21(1), 1-46 (1989; Zbl 0681.03020)], where the authors ask ``to further develop ideas from recursive function theory such as fixed point theorems, reducibilities and hierarchies for machines over a ring \(R\)''.