Classifying the computational power of stochastic physical oracles
- Submitting institution
-
Swansea University / Prifysgol Abertawe
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 43498
- Type
- D - Journal article
- DOI
-
-
- Title of journal
- International Journal of Unconventional Computing
- Article number
- -
- First page
- 59
- Volume
- 14
- Issue
- 1
- ISSN
- 1548-7199
- Open access status
- Compliant
- Month of publication
- December
- Year of publication
- 2018
- URL
-
https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-14-number-1-2018/ijuc-14-1-p-59-90/
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
-
- Research group(s)
-
-
- Citation count
- 0
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- What are the computational limits of algorithms whose inputs and parameters come directly from physical measurements? Our classification of measurement methods, types of error, and notions of time for deterministic systems left the open problem for nondeterministic measurements that this paper solves. Thus, this paper on nondeterministic stochastic physical measurements completes the evidence for our decade-old (2010) Conjecture that, while polynomial time analogue-digital computational systems break the Turing barrier, their computational limit is the non-uniform complexity class BPP//log* (e.g., see the progress report for deterministic systems International Journal of Foundations of Computer Science, 25 (2014), 373–389).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -