No Cover Image

Book Chapter 383 views

A Hierarchy for $$ BPP //\log \!\star $$ B P P / / log ⋆ Based on Counting Calls to an Oracle / Edwin Beggs; Pedro Cortez; José Félix Costa; John V Tucker

Emergent Computation, Volume: 24, Pages: 39 - 56

Swansea University Author: Tucker, John

Full text not available from this repository: check for access using links below.

Abstract

Algorithms whose computations involve making physical measurementscan be modelled by Turing machines with oracles that are physical systems and oraclequeries that obtain data from observation and measurement. The computationalpower of many of these physical oracles has been established using non-uni...

Full description

Published in: Emergent Computation
ISBN: 978-3-319-46375-9 978-3-319-46376-6
ISSN: 2194-7287 2194-7295
Published: Springer 2016
Online Access: Check full text

URI: https://cronfa.swan.ac.uk/Record/cronfa31353
Tags: Add Tag
No Tags, Be the first to tag this record!
Abstract: Algorithms whose computations involve making physical measurementscan be modelled by Turing machines with oracles that are physical systems and oraclequeries that obtain data from observation and measurement. The computationalpower of many of these physical oracles has been established using non-uniform complexityclasses; in particular, for large classes of deterministic physical oracles, withfixed error margins constraining the exchange of data between algorithm and oracle,the computational power has been shown to be the non-uniform class BPP// log*.In this paper, we consider non-deterministic oracles that can be modelled by randomwalks on the line.We show how to classify computations within BPP// log* bymaking an infinite non-collapsing hierarchy between BPP// log* and BPP. The hierarchyrests on the theorem that the number of calls to the physical oracle correlateswith the size of the responses to queries.
Keywords: Turing machines, physical oracles, non-uniform complexity classes, BPP, hierarchies
College: College of Science
Start Page: 39
End Page: 56