Transactions of the American Mathematical Society · 1985 · 58 citations · 13 references
ComputingComputer ScienceMathematicsAlgorithmsFormal MethodsTheory Of ComputationComputational ComplexityFinite-state MachinesTuring MachinesAnnotation EncodingDeterministic SimulationDeterministic Turing MachinesLower BoundsNondeterministic ComplexityNondeterministic Turing MachinesTuring Machine CharacterizationsWorst-case Bounds
We introduce new techniques for proving quadratic lower bounds for deterministic and nondeterministic <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1"> <mml:semantics> <mml:mn>1</mml:mn> <mml:annotation encoding="application/x-tex">1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -tape Turing machines (all considered Turing machines have an additional one-way input tape). In particular, we derive for the simulation of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2"> <mml:semantics> <mml:mn>2</mml:mn> <mml:annotation encoding="application/x-tex">2</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -tape Turing machines by <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1"> <mml:semantics> <mml:mn>1</mml:mn> <mml:annotation encoding="application/x-tex">1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -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 [ <bold>3</bold> ]). Further, we demonstrate a substantial superiority of nondeterminism over determinism and of co-nondeterminism over nondeterminism for <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1"> <mml:semantics> <mml:mn>1</mml:mn> <mml:annotation encoding="application/x-tex">1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> -tape Turing machines.
13
Two-Tape Simulation of Multitape Turing Machines
F. C. Hennie, Richard E. Stearns · Journal of the ACM · 1966 · 287 citations · Full text
One-tape, off-line Turing machine computations
F. C. Hennie · Information and Control · 1965 · 227 citations