In this paper, we consider a new direction of computation, which we call computation with large advice. We mainly consider constant space computation with large advice in Turing machines, and prove the following facts: (i) The class of decision problems solvable by a constant space Turing machine with polynomial-size advice includes nonuniform-{\sf NC}$^1$, (ii) The class of decision problems solvable by a constant space Turing machine with quasipolynomial-size advice equals nonuniform-{\sf polyL}. The facts mean constant space computation with large advice has unexpected computational power. On the other hand, we mention bounded time computation with large advice, and attempt to propose a concept of ``algorithms with large advice''. In the proposal, advice is precomputed data for a problem and a fixed instance size, and we expect efficient algorithms by large or huge advice.
翻译：在这篇论文中，我们考虑了一种新的计算方向，称为使用大型建议的计算。我们主要考虑Constant Space Turing机中的大型建议的计算，证明了以下事实：（i）通过具有多项式大小建议的Constant Space Turing机可解决的决策问题包括非均匀 $\sf NC^1$ （ii）通过具有准多项式大小建议的Constant Space Turing机可解决的决策问题等于非均匀 $\sf polyL$。这些事实意味着使用大型建议的Constant Space计算具有出乎意料的计算能力。另一方面，我们提及具有大型建议的有界时间计算，并尝试提出“具有大型建议的算法”的概念。在这一提案中，建议是问题和固定实例大小的预计算数据，我们期望通过大型或巨大的建议实现高效算法。
相关内容
微信扫码咨询专知VIP会员