On the Power of Real Turing Machines over Binary Inputs

DOI10.1137/S0097539794270340zbMath0874.68110OpenAlexW2048353152MaRDI QIDQ4337443

Felipe Cucker, Dima Yu. Grigoriev

Publication date: 10 November 1997

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794270340

zbMATH Keywords

real Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Nearly sharp complexity bounds for multiprocessor algebraic computations, Cook's versus Valiant's hypothesis, Semidefinite programming and arithmetic circuit evaluation, On the computation of Boolean functions by analog circuits of bounded fan-in, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, On a transfer theorem for the \(\text{P}\neq \text{NP}\) conjecture, Exotic quantifiers, complexity classes, and complete problems, VPSPACE and a transfer theorem over the complex field, Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics, Saturation and stability in the theory of computation over the reals, Real computations with fake numbers, Transfer theorems via sign conditions