
arXiv: 1606.06803
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 Proceedings PC 2016, arXiv:1606.06513
FOS: Computer and information sciences, Computer Science - Computational Complexity, Electronic computers. Computer science, QA1-939, QA75.5-76.95, Computational Complexity (cs.CC), Mathematics
FOS: Computer and information sciences, Computer Science - Computational Complexity, Electronic computers. Computer science, QA1-939, QA75.5-76.95, Computational Complexity (cs.CC), Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
