Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines
Author:
Wolfgang Maass
Journal:
Trans. Amer. Math. Soc. 292 (1985), 675693
MSC:
Primary 03D15; Secondary 03D10, 68Q15, 94A17
MathSciNet review:
808746
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We introduce new techniques for proving quadratic lower bounds for deterministic and nondeterministic tape Turing machines (all considered Turing machines have an additional oneway input tape). In particular, we derive for the simulation of tape Turing machines by 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 conondeterminism over nondeterminism for tape Turing machines.
 [1]
Ronald
V. Book, Sheila
A. Greibach, and Ben
Wegbreit, Time and tapebounded Turing acceptors and
𝐴𝐹𝐿𝑠, J. Comput. System Sci.
4 (1970), 606–621. MR 0267993
(42 #2893)
 [2]
P. Duris and Z. Galil, Two tapes are better than one for nondeterministic machines, Proc. 14th ACM STOC (1982), 17.
 [3]
P. Duris, Z. Galil, W. J. Paul and R. Reischuk, Two nonlinear lower bounds, Proc. 15th ACM STOC, 1983, pp. 127132.
 [4]
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
(83g:68097)
 [5]
Z. Galil, private communication
 [6]
P. R. Halmos, Ergodic theory, Lecture Notes, University of Chicago, 1955.
 [7]
J.
Hartmanis and R.
E. Stearns, On the computational complexity of
algorithms, Trans. Amer. Math. Soc. 117 (1965), 285–306. MR 0170805
(30 #1040), http://dx.doi.org/10.1090/S00029947196501708057
 [8]
F.
C. Hennie, Onetape, offline Turing machine computations,
Information and Control 8 (1965), 553–578. MR 0191769
(32 #9171)
 [9]
F.
C. Hennie and R.
E. Stearns, Twotape simulation of multitape Turing machines,
J. Assoc. Comput. Mach. 13 (1966), 533–546. MR 0210521
(35 #1413)
 [10]
John
E. Hopcroft and Jeffrey
D. Ullman, Introduction to automata theory, languages, and
computation, AddisonWesley Publishing Co., Reading, Mass., 1979.
AddisonWesley Series in Computer Science. MR 645539
(83j:68002)
 [11]
R. Kannan, Alternation and the power of nondeterminism, Proc. 15th ACM STOC, 1983, pp. 344346.
 [12]
M. Klawe, Nonexistence of onedimensional expanding graphs, Proc. 22th IEEE FOCS, 1981, pp. 109113.
 [13]
M. Li, On one tape versus two stacks, preprint (February 1984).
 [14]
W. Maass, Simulation of two tapes by one tape requires quadratic time, abstract (August 1983).
 [15]
, Quadratic lower bounds for deterministic and nondeterministic Turing machines, abstract (September 1983).
 [16]
, Are recursion theoretic arguments useful in complexity theory (Proc. Internat. Conf. on Logic, Methodology and Philosophy of Science, Salzburg, 1983), NorthHolland, Amsterdam, 1983.
 [17]
, Quadratic lower bounds for deterministic and nondeterministic onetape Turing machines, Proc. 16th ACM STOC, 1984, pp. 401408.
 [18]
, An optimal lower bound for random access machines and other applications of Ramsey's theorem, abstract (June 1984).
 [19]
, Meanders, Ramsey's theorem and lower bound arguments (in preparation).
 [20]
W. Maass and A. Schorr, Speedup of onetape Turing machines by bounded alternation (in preparation).
 [21]
W.
Paul, Online simulation of 𝑘+1 tapes by 𝑘 tapes
requires nonlinear time, 23rd annual symposium on foundations of
computer science (Chicago, Ill., 1982) IEEE, New York, 1982,
pp. 53–56. MR
780380
 [22]
W. J. Paul, N. Pippenger, E. Szemeredi and W. Trotter, On determinism versus nondeterminism and related problems, Proc. 24th IEEE FOCS, 1983, pp. 429438.
 [23]
Michael
O. Rabin, Real time computation, Israel J. Math.
1 (1963), 203–211. MR 0163849
(29 #1148)
 [24]
P. M. B. Vitányi, One queue or two pushdown stores take square time on a onehead tape unit, Report CSR8406 of the Centre for Mathematics and Computer Science, Amsterdam, 1984.
 [1]
 R. V. Book, S. A. Greibach and B. Wegbreit, Time and tape bounded Turing acceptors and 's, J. Comput. System Sci. 4 (1970), 606621. MR 0267993 (42:2893)
 [2]
 P. Duris and Z. Galil, Two tapes are better than one for nondeterministic machines, Proc. 14th ACM STOC (1982), 17.
 [3]
 P. Duris, Z. Galil, W. J. Paul and R. Reischuk, Two nonlinear lower bounds, Proc. 15th ACM STOC, 1983, pp. 127132.
 [4]
 O. Gabber and Z. Galil, Explicit constructions of linear size superconcentrators, Proc. 20th IEEE FOCS, 1979, pp. 364370. MR 598118 (83g:68097)
 [5]
 Z. Galil, private communication
 [6]
 P. R. Halmos, Ergodic theory, Lecture Notes, University of Chicago, 1955.
 [7]
 J. Hartmanis and R. E. Stearns, On the computational and complexity of algorithms, Trans. Amer. Math. Soc. 117 (1965), 285306. MR 0170805 (30:1040)
 [8]
 F. C. Hennie, Onetape offline Turing machine computations, Inform. and Control 8 (1965), 553578. MR 0191769 (32:9171)
 [9]
 F. C. Hennie and R. E. Stearns, Twotape simulation of multitape Turing machines, J. Assoc. Comput. Mach. 13 (1966), 533546. MR 0210521 (35:1413)
 [10]
 J. E. Hopcroft and J. D. Ullman, Introduction to automata theory, languages and computation, AddisonWesley, Reading, Mass., 1979. MR 645539 (83j:68002)
 [11]
 R. Kannan, Alternation and the power of nondeterminism, Proc. 15th ACM STOC, 1983, pp. 344346.
 [12]
 M. Klawe, Nonexistence of onedimensional expanding graphs, Proc. 22th IEEE FOCS, 1981, pp. 109113.
 [13]
 M. Li, On one tape versus two stacks, preprint (February 1984).
 [14]
 W. Maass, Simulation of two tapes by one tape requires quadratic time, abstract (August 1983).
 [15]
 , Quadratic lower bounds for deterministic and nondeterministic Turing machines, abstract (September 1983).
 [16]
 , Are recursion theoretic arguments useful in complexity theory (Proc. Internat. Conf. on Logic, Methodology and Philosophy of Science, Salzburg, 1983), NorthHolland, Amsterdam, 1983.
 [17]
 , Quadratic lower bounds for deterministic and nondeterministic onetape Turing machines, Proc. 16th ACM STOC, 1984, pp. 401408.
 [18]
 , An optimal lower bound for random access machines and other applications of Ramsey's theorem, abstract (June 1984).
 [19]
 , Meanders, Ramsey's theorem and lower bound arguments (in preparation).
 [20]
 W. Maass and A. Schorr, Speedup of onetape Turing machines by bounded alternation (in preparation).
 [21]
 W. J. Paul. Online simulation of tapes by tapes requires nonlinear time, Proc. 23rd IEEE FOCS, 1982, pp. 5356. MR 780380
 [22]
 W. J. Paul, N. Pippenger, E. Szemeredi and W. Trotter, On determinism versus nondeterminism and related problems, Proc. 24th IEEE FOCS, 1983, pp. 429438.
 [23]
 M. O. Rabin, Real time computation, Israel J. Math. 1 (1963), 203211. MR 0163849 (29:1148)
 [24]
 P. M. B. Vitányi, One queue or two pushdown stores take square time on a onehead tape unit, Report CSR8406 of the Centre for Mathematics and Computer Science, Amsterdam, 1984.
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
03D15,
03D10,
68Q15,
94A17
Retrieve articles in all journals
with MSC:
03D15,
03D10,
68Q15,
94A17
Additional Information
DOI:
http://dx.doi.org/10.1090/S00029947198508087464
PII:
S 00029947(1985)08087464
Article copyright:
© Copyright 1985
American Mathematical Society
