Two \(P\)-complete problems in the theory of the reals
type: Item
instance of: scholarly article
title: Two \(P\)-complete problems in the theory of the reals
zbMATH Open document ID: 0759.68032
DOI: 10.1016/0885-064X(92)90008-Y
author: A. Torrecillas
author: Felipe Cucker
published in: Journal of Complexity
publication date: 1993-02-22T00:00:00Z
review text: 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\)''.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 120256
zbMATH Keywords: algebraic complexity
zbMATH Keywords: parallel complexity classes
zbMATH Keywords: PRAM
zbMATH Keywords: parallel algorithms over the reals
zbMATH Keywords: real circuit decision problem
zbMATH Keywords: systems of equations solvable by substitution
MaRDI profile type: Publication
Wikidata QID: Q57733324
cites work: On the computational power of pushdown automata
cites work: Q3692867
cites work: On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
cites work: Q3770650
cites work: \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
cites work: Q4725742
cites work: Complete problems for deterministic polynomial time
cites work: Q4385522
cites work: Q3694703
cites work: Simulation of Parallel Random Access Machines by Circuits
description: scientific article; zbMATH DE number 120256