Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape

DOI10.1007/S000370050006zbMath0962.68066OpenAlexW1978013003MaRDI QIDQ1587349

Martin Dietzfelbinger, Martin Hühne

Publication date: 20 November 2000

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050006

zbMATH Keywords

Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (1)

A time lower bound for satisfiability

This page was built for publication: Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape