A leaf-size hierarchy of three-dimensional alternating turing Machines

概要

論文の詳細を見る
Alternating Turing machines were introduced as a generalization of nondeterministic Turing machines and as a mechanism to model parallel computation. ”Leaf-size” (or ”branching”) is the minimum number of leaves of some accepting computation trees of alternating Turing machines. Leaf-size, in a sense, reflects the minimum number of processors that run in parallel in accepting a given input. In this paper, we investigate a hierarchy of complexity classes based on leaf-size bounded computations for three-dimensional alternating Turing machines, and show that for any positive integer k＞__-1 and for any two functions L: N→N and L': N→N such that (1) L is a three-dimensionally space-constructible function such that L (m)^<k+1>＜__- m (m＞__-;1), (2) lim_<m→∞>L(m)L'(m)^k/log m=0 and (3) lim_<m→∞>L'(m)/L(m)=0, L(m) space bounded and L(m)^k leaf-size bounded three-dimensional alternating Turing machines are more powerful than L (m) space bounded and L'(m)^k leaf-size bounded three-dimensional alternating Turing machines. We let the input tapes, throughout this paper, be restricted to cubic ones.
山口大学の論文