The impact of models of a physical oracle on computational power
Using physical experiments as oracles for algorithms, we can characterise the
computational power of classes of physical systems. Here we show that two different
physical models of the apparatus for a single experiment can have different computational
power. The experiment is the scatter machine experiment (SME), which was first presented
in Beggs and Tucker (2007b). Our first physical model contained a wedge with a sharp
vertex that made the experiment non-deterministic with constant runtime. We showed that …
computational power of classes of physical systems. Here we show that two different
physical models of the apparatus for a single experiment can have different computational
power. The experiment is the scatter machine experiment (SME), which was first presented
in Beggs and Tucker (2007b). Our first physical model contained a wedge with a sharp
vertex that made the experiment non-deterministic with constant runtime. We showed that …
Using physical experiments as oracles for algorithms, we can characterise the computational power of classes of physical systems. Here we show that two different physical models of the apparatus for a single experiment can have different computational power. The experiment is the scatter machine experiment (SME), which was first presented in Beggs and Tucker (2007b). Our first physical model contained a wedge with a sharp vertex that made the experiment non-deterministic with constant runtime. We showed that Turing machines with polynomial time and an oracle based on a sharp wedge computed the non-uniform complexity class P/poly. Here we reconsider the experiment with a refined physical model where the sharp vertex of the wedge is replaced by any suitable smooth curve with vertex at the same point. These smooth models of the experimental apparatus are deterministic. We show that no matter what shape is chosen for the apparatus: (i) the time of detection of the scattered particles increases at least exponentially with the size of the query; and(ii) Turing machines with polynomial time and an oracle based on a smooth wedge compute the non-uniform complexity class P/log* ⫋ P/poly. We discuss evidence that many experiments that measure quantities have exponential runtimes and a computational power of P/log*.
Cambridge University Press
以上显示的是最相近的搜索结果。 查看全部搜索结果