On the Power of Real Turing Machines over Binary Inputs

DOI10.1137/S0097539794270340MaRDI QIDQ4337443zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

real Turing machines

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(12)

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

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)