Machines Over the Reals and Non-Uniformity

DOI10.1002/MALQ.19970430202MaRDI QIDQ4336697zbMATHOpenAlexFDO

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

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)

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

(3)

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

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)