An Atemporal Model of Physical Complexity

Richard Whyman
(The University of Leeds)

We present the finite first-order theory (FFOT) machine, which provides an atemporal description of computation. We then develop a concept of complexity for the FFOT machine, and prove that the class of problems decidable by a FFOT machine with polynomial resources is NP intersect co-NP.

In Michael Cuffaro and Philippos Papayannopoulos: Proceedings of the 9th International Workshop on Physics and Computation (PC 2018), Fontainebleau, France, 26 June 2018, Electronic Proceedings in Theoretical Computer Science 273, pp. 39–51.
Published: 2nd July 2018.

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