Physical Computation, P/poly and P/log*

Richard Whyman
(The University of Leeds)

In this paper we give a framework for describing how abstract systems can be used to compute if no randomness or error is involved. Using this we describe a class of classical "physical" computation systems whose computational capabilities in polynomial time are equivalent to P/poly. We then extend our framework to describe how measurement and transformation times may vary depending on their input. Finally we describe two classes of classical "physical" computation systems in this new framework whose computational capabilities in polynomial time are equivalent to P/poly and P/log*.

In Alastair A. Abbott and Dominic C. Horsman: Proceedings of the 7th International Workshop on Physics and Computation (PC 2016), Manchester, UK, 14 July 2016, Electronic Proceedings in Theoretical Computer Science 214, pp. 41–52.
Published: 21st June 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.214.7 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org