Simulating two pushdown stores by one tape in 0(n1.5√log n) time

摘要

Based on graph separator theorems, we develop a new simulation technique which allows us to resolve several open problems for on-line computations: (1)One tape can nondeterministically simulate two nondeterministic pushdown stores in 0(n1.5√log n) time. Together with the Ω(n1.5/trlog n)lower bound, this solves the open problem 1 in P. Duris et al. (“Proceedings, 15th ACM Symp. on Theory of Computing, 1983,” pp. 127–132) for the one-tape versus two pushdown store case. It also disproves the conjectured Ω(n2) lower bound which holds in the deterministic case (W. Maass, Trans. Amer. Math. Soc.292 (1985), 675–693; M. Li and P. B. M. Vitanyi, Inform. and Computation, in press.) (2) The languages actually used by Maass and Freivalds (Inform. Process.77 (1977), 839–842) can be accepted in O(n2log log n/√log n) and O(n1.5/trlog n) time by a one-tape TM, respectively. Therefore they cannot be used to obtain the Ω(n2) lower bound for one tape nondeterministically simulating two tapes. The algorithm depends on a new graph separator theorem. (3) Three pushdown stores are better than two pushdown stores for nondeterministic machines. This anwwers a rather old open problem of R. V. Book and S. A. Greibach (Math. Systems Theory4 (1970), 97–111) and P. Duris and Z. Galil (in “Proceedings, 14th ACM Symp. on Theory of Comput., 1982,” pp. 1–7). (4) One tape can nondeterministically simulate one nondeterministic queue in 0(n1.5√log n) time. This disproves the conjectured Ω(n2) lower bound which holds in the deterministic case.