Relationships between time‐leaf‐and‐space bounded ATMS and reversal‐and‐space bounded NTMs
Hiroaki Yamamoto, Shoichi Noguchi · Systems and Computers in Japan · 1985
Abstract Until now, discussions have been made for several models of deterministic parallel computation, concerning such items as the trade‐off between the time and the number of processors and the relations among those models. However, few discussions have been made for the nondeterministic case. This paper discusses the nondeterministic case, using ATM (alternating Turing machine) and NTM (nondeterministic Turing machine). The main results are as follows. (1) WhenR(n)=0(S(n)), andR(n)=ω(log(S(n)),S(n) = ω (n), NRS,(Ro(1)(n) andS0(1)(n)) ATBS(R0(1)(n),S0(1)(n),R0(1)(n))NRSR0(1)(n)),S0(1)(n),S0(1)(n)). (2) S(n) = 0(R(n)) andS(n)=ω (log(R(n)),R(n) = ω(n), where NRSR0(1)(n),S0(1)(n))=ATBSR0(1)(n)),S0(1)(n)), where NRS(R(n),S(n) (ATBS )T(n),B(n), S(n)is the class of languages accepted by(R(n),S(n))reversal‐and‐space bounded NTM[(T(n),B(n)]time‐leaf‐and‐space bounded ATM).