论文标题
最小的速度设置
A minimal set low for speed
论文作者
论文摘要
如果Oracle $ a $无法加快已经可以计算的集合的计算，则它是可计算的：如果可以使用$ a $作为甲骨文在时间$ t（n）$中确定可决定性的语言，那么对于某些多义$ p $，可以在时间$ p（t（n））中在时间$ p（t（n））中确定它。拜耳和斯拉曼首先展示了一个低速度的集合的存在，他们构建了一个不可计算的计算台集，该集合是低速度的。在本文中，我们回答了Bienvenu和Downey先前提出的一个问题，他们询问是否有最低速度的速度。通过强迫构建一组最小程度的标准方法与使设定的低速度速度不相容。但是，我们能够使用强迫和完整近似的有趣的新组合来构建一个既是最小程度又低速度的集合。
An oracle $A$ is low-for-speed if it is unable to speed up the computation of a set which is already computable: if a decidable language can be decided in time $t(n)$ using $A$ as an oracle, then it can be decided without an oracle in time $p(t(n))$ for some polynomial $p$. The existence of a set which is low-for-speed was first shown by Bayer and Slaman who constructed a non-computable computably enumerable set which is low-for-speed. In this paper we answer a question previously raised by Bienvenu and Downey, who asked whether there is a minimal degree which is low-for-speed. The standard method of constructing a set of minimal degree via forcing is incompatible with making the set low-for-speed; but we are able to use an interesting new combination of forcing and full approximation to construct a set which is both of minimal degree and low-for-speed.
