Machines Over the Reals and Non-Uniformity

DOI10.1002/MALQ.19970430202zbMATH Open0941.03038OpenAlexW2054738961MaRDI QIDQ4336697FDOQ4336697

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

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

zbMATH Keywords

surveycomplexity theorypolynomial time computabilitynon-uniform complexityreal computabilitypolynomial time hierarchydecision problems over a finite alphabetpolynomial advicepower of real machines over binary inputsreal complexity class

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• On the complexity of nonuniform wavelength-based machine
• A machine producing non-*Lindelöf spaces
• Some aspects of studying an optimization or decision problem in different computational models

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)