Computational complexity with experiments as oracles. II. Upper bounds

• Tipo: Artigo em Revista Científica Internacional
• Data: 2009

Autores

Beggs, E (Autor) Outra; Costa, JF (Autor) Outra; Loff, B (Autor) Outra; Tucker, JV (Autor) Outra

Revista

Título: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences

Vol. 465

Páginas: 1453-1465

ISSN: 1364-5021

Editora: The Royal Society

Indexação

ISI Web of Knowledge - 18 Citações

Scopus - 17 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13