Computational complexity with experiments as oracles. II. Upper bounds

DOI10.1098/RSPA.2008.0412zbMath1186.68194OpenAlexW2146870677MaRDI QIDQ3561915

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

Publication date: 19 May 2010

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

Full work available at URL: http://rspa.royalsocietypublishing.org/content/vol465/issue2105/

zbMATH Keywords

experimental procedurenon-uniform complexityTuring machines with oraclesalgorithmic procedureanalogue-digital computationphysical oracles

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)

Related Items (9)

The impact of models of a physical oracle on computational power ⋮ AN ANALOGUE-DIGITAL CHURCH-TURING THESIS ⋮ Machines that perform measurements ⋮ Computations with oracles that measure vanishing quantities ⋮ The Power of Machines That Control Experiments ⋮ 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 ⋮ Computations via Newtonian and relativistic kinematic systems

Cites Work

• Experimental computation of real numbers by Newtonian machines
• Computational complexity with experiments as oracles

This page was built for publication: Computational complexity with experiments as oracles. II. Upper bounds