Computational complexity with experiments as oracles. II. Upper bounds

• Type: Article in International Scientific Journal
• Date: 2009

Authors

Beggs, E (Author) Other; Costa, JF (Author) Other; Loff, B (Author) Other; Tucker, JV (Author) Other

Journal

Title: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

Vol. 465

Pages: 1453-1465

ISSN: 1364-5021

Publisher: The Royal Society

Indexing

ISI Web of Knowledge - 18 Citations

Scopus - 17 Citations

Other information

Authenticus ID: P-003-K4G

DOI: 10.1098/rspa.2008.0412

Abstract (EN): Earlier, to explore the idea of combining physical experiments with algorithms, we introduced a new form of analogue digital (AD) Turing machine. We examined in detail a case study where an experimental procedure, based on Newtonian kinematics, is used as an oracle with classes of Turing machines. The physical cost of oracle calls was counted and three forms of AD queries were studied, in which physical parameters can be set exactly and approximately. Here, in this sequel, we complete the classi. cation of the computational power of these AD Turing machines and determine precisely what they can compute, using non- uniform complexity classes and probabilities.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13