On the Power of Real Turing Machines over Binary Inputs

DOI10.1137/S0097539794270340zbMATH Open0874.68110OpenAlexW2048353152MaRDI QIDQ4337443FDOQ4337443

Authors: Felipe Cucker, Dima 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

Recommendations

• Machines Over the Reals and Non-Uniformity
• \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\)
• Computing over the reals with addition and order

zbMATH Keywords

real Turing machines

Mathematics Subject Classification ID

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

Cited In (12)

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

This page was built for publication: On the Power of Real Turing Machines over Binary Inputs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4337443)