Machines Over the Reals and Non-Uniformity

DOI10.1002/MALQ.19970430202MaRDI QIDQ4336697zbMATH OpenOpenAlexFDO

Authors Felipe Cucker

Publication date 14 May 1997

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19970430202

zbMATH Keywords

complexity theorydecision problems over a finite alphabetnon-uniform complexitypolynomial advicepolynomial time computabilitypolynomial time hierarchypower of real machines over binary inputsreal complexity classreal computabilitysurvey

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the Power of Real Turing Machines over Binary Inputs
• \(\text{P}\neq \text{NP}\) for the reals with various analytic functions
• Computing over the reals with addition and order

Cites work

• Bounds for the computational power and learning complexity of analog neural nets
• Computing over the reals with addition and order: Higher complexity classes
• On the complexity of integer programming

Cited in

(5)

• A machine producing non-*Lindelöf spaces
• On the cost of uniform and nonuniform algorithms
• Some aspects of studying an optimization or decision problem in different computational models
• On the complexity of nonuniform wavelength-based machine
• On the Power of Real Turing Machines over Binary Inputs

This page was built for publication: Machines Over the Reals and Non-Uniformity

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