Output details
11 - Computer Science and Informatics
Swansea University
Article title
Computational complexity with experiments as oracles
Type
D - Journal article
Title of journal
Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Article number
-
Volume number
464
Issue number
2098
First page of article
2777
ISSN of journal
1471-2946
Year of publication
2008
URL
-
Number of additional authors
3
Additional information
<10> The first theory to use physical systems as oracles to algorithms, and classify their computational power, since Turing introduced oracles in 1939. We introduce three types of query errors and data-dependent waiting times, changing Post’s 1944 error-free unit-time queries. The methods are further developed in 12 papers. The paper contains lower bound theorems; due to page limits, the upper bounds are in a sequel: Proceedings Royal Society Series A, 465 (2009) 1453-1465. The paper is the subject of many invited lectures and an invited course at the Physics and Computation workshop at the 10th Unconventional Computation, Turku, 2011.
Interdisciplinary
-
Cross-referral requested
-
Research group
A - Theoretical Computer Science
Citation count
12
Proposed double-weighted
No
Double-weighted statement
-
Reserve for a double-weighted output
No
Non-English
No
English abstract
-
