Machines Over the Reals and Non-Uniformity

DOI10.1002/malq.19970430202zbMath0941.03038OpenAlexW2054738961MaRDI QIDQ4336697

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) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Related Items (1)

Some aspects of studying an optimization or decision problem in different computational models

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

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