Two P-complete problems in the theory of the reals (Q4036593)

[For the entire collection see Zbl 0753.00027.] ``A classical subject in computational complexity is what is usually called algebraic complexity. This area deals with the complexity of algorithms take that their inputs on \(R^ n\), where \(R\) is a ring, understood as the number of ring operations the algorithm performs as a function of \(n\) and the main kind of results are both upper and lower bounds. A very special case in algebraic complexity is the one dealing with \(R=\mathbb{R}\). Here, the assumption that all the elements in the field have unit size, and that the cost of the field operations is also unitary, reflects the particular features of algorithms in numerical analysis. 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. On the one hand, the evaluation of algebraic circuits that have sign gates. On the other hand, the solution of systems of equalities and inequalities via substitutions''.