Computational complexity with experiments as oracles

DOI10.1098/RSPA.2008.0085zbMath1152.68444OpenAlexW2127076297MaRDI QIDQ5505107

Bruno Loff, Costa, José Félix, J. V. Tucker, Edwin J. Beggs

Publication date: 23 January 2009

Published in: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1098/rspa.2008.0085

zbMATH Keywords

experimental procedurenon-uniform complexityTuring machines with oraclesalgorithmic procedureanalogue-digital computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (16)

The impact of models of a physical oracle on computational power ⋮ AN ANALOGUE-DIGITAL CHURCH-TURING THESIS ⋮ Physical oracles: the Turing machine and the Wheatstone bridge ⋮ Machines that perform measurements ⋮ Computations with oracles that measure vanishing quantities ⋮ The Power of Machines That Control Experiments ⋮ Programming Experimental Procedures for Newtonian Kinematic Machines ⋮ Oracles and Advice as Measurements ⋮ Computational complexity with experiments as oracles. II. Upper bounds ⋮ THREE FORMS OF PHYSICAL MEASUREMENT AND THEIR COMPUTABILITY ⋮ A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle ⋮ Limits to measurement in experiments governed by algorithms ⋮ The computational status of physics ⋮ Computations via Newtonian and relativistic kinematic systems ⋮ Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics ⋮ A Survey on Analog Models of Computation

Cites Work

• Can Newtonian systems, bounded in space, time, mass and energy compute all functions?
• The wave equation with computable initial data such that its unique solution is not computable
• The structure of logarithmic advice complexity classes
• On the computational power of dynamical systems and hybrid systems
• Analog computers and recursive functions over the reals.
• The differential analyzer. A new machine for solving differential equations
• Why there is no such discipline as hypercomputation
• Embedding infinitely parallel computation in Newtonian kinematics
• IS WAVE PROPAGATION COMPUTABLE OR CAN WAVE COMPUTERS BEAT THE TURING MACHINE?
• Classical physics and the Church--Turing Thesis
• Computable and Continuous Partial Homomorphisms on Metric Partial Algebras
• Experimental computation of real numbers by Newtonian machines
• Mathematical Theory of the Differential Analyzer

This page was built for publication: Computational complexity with experiments as oracles