Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society, the Transactions of the American Mathematical Society (TRAN) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.43.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines
HTML articles powered by AMS MathViewer

by Wolfgang Maass PDF
Trans. Amer. Math. Soc. 292 (1985), 675-693 Request permission

Abstract:

We introduce new techniques for proving quadratic lower bounds for deterministic and nondeterministic $1$-tape Turing machines (all considered Turing machines have an additional one-way input tape). In particular, we derive for the simulation of $2$-tape Turing machines by $1$-tape Turing machines an optimal quadratic lower bound in the deterministic case and a nearly optimal lower bound in the nondeterministic case. This answers the rather old question whether the computing power of the considered types of Turing machines is significantly increased when more than one tape is used (problem Nos. 1 and 7 in the list of Duris, Galil, Paul, Reischuk [3]). Further, we demonstrate a substantial superiority of nondeterminism over determinism and of co-nondeterminism over nondeterminism for $1$-tape Turing machines.
References
  • Ronald V. Book, Sheila A. Greibach, and Ben Wegbreit, Time- and tape-bounded Turing acceptors and $\textrm {AFLs}$, J. Comput. System Sci. 4 (1970), 606โ€“621. MR 267993, DOI 10.1016/S0022-0000(70)80031-9
  • P. Duris and Z. Galil, Two tapes are better than one for nondeterministic machines, Proc. 14th ACM STOC (1982), 1-7. P. Duris, Z. Galil, W. J. Paul and R. Reischuk, Two nonlinear lower bounds, Proc. 15th ACM STOC, 1983, pp. 127-132.
  • Ofer Gabber and Zvi Galil, Explicit constructions of linear size superconcentrators, 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979) IEEE, New York, 1979, pp.ย 364โ€“370. MR 598118
  • Z. Galil, private communication P. R. Halmos, Ergodic theory, Lecture Notes, University of Chicago, 1955.
  • J. Hartmanis and R. E. Stearns, On the computational complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285โ€“306. MR 170805, DOI 10.1090/S0002-9947-1965-0170805-7
  • F. C. Hennie, One-tape, off-line Turing machine computations, Information and Control 8 (1965), 553โ€“578. MR 191769
  • F. C. Hennie and R. E. Stearns, Two-tape simulation of multitape Turing machines, J. Assoc. Comput. Mach. 13 (1966), 533โ€“546. MR 210521, DOI 10.1145/321356.321362
  • John E. Hopcroft and Jeffrey D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley Publishing Co., Reading, Mass., 1979. MR 645539
  • R. Kannan, Alternation and the power of nondeterminism, Proc. 15th ACM STOC, 1983, pp. 344-346. M. Klawe, Non-existence of one-dimensional expanding graphs, Proc. 22th IEEE FOCS, 1981, pp. 109-113. M. Li, On one tape versus two stacks, preprint (February 1984). W. Maass, Simulation of two tapes by one tape requires quadratic time, abstract (August 1983). โ€”, Quadratic lower bounds for deterministic and nondeterministic Turing machines, abstract (September 1983). โ€”, Are recursion theoretic arguments useful in complexity theory (Proc. Internat. Conf. on Logic, Methodology and Philosophy of Science, Salzburg, 1983), North-Holland, Amsterdam, 1983. โ€”, Quadratic lower bounds for deterministic and nondeterministic one-tape Turing machines, Proc. 16th ACM STOC, 1984, pp. 401-408. โ€”, An optimal lower bound for random access machines and other applications of Ramseyโ€™s theorem, abstract (June 1984). โ€”, Meanders, Ramseyโ€™s theorem and lower bound arguments (in preparation). W. Maass and A. Schorr, Speed-up of one-tape Turing machines by bounded alternation (in preparation).
  • W. Paul, On-line simulation of $k+1$ tapes by $k$ tapes requires nonlinear time, 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982) IEEE, New York, 1982, pp.ย 53โ€“56. MR 780380
  • W. J. Paul, N. Pippenger, E. Szemeredi and W. Trotter, On determinism versus nondeterminism and related problems, Proc. 24th IEEE FOCS, 1983, pp. 429-438.
  • Michael O. Rabin, Real time computation, Israel J. Math. 1 (1963), 203โ€“211. MR 163849, DOI 10.1007/BF02759719
  • P. M. B. Vitรกnyi, One queue or two pushdown stores take square time on a one-head tape unit, Report CS-R8406 of the Centre for Mathematics and Computer Science, Amsterdam, 1984.
Similar Articles
Additional Information
  • © Copyright 1985 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 292 (1985), 675-693
  • MSC: Primary 03D15; Secondary 03D10, 68Q15, 94A17
  • DOI: https://doi.org/10.1090/S0002-9947-1985-0808746-4
  • MathSciNet review: 808746