A note on square rooting of time functions of Turing machines

DOI10.1007/S00224-002-1079-XMaRDI QIDQ1405791zbMATH OpenOpenAlexFDO

Authors Richard J. Lipton, Yechezkel Zalcstein, Ogihara, Mitsunori

Publication date 26 August 2003

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-002-1079-x

zbMATH Keywords

deterministic Turing machine

Mathematics Subject Classification ID

Recommendations

• On proving time constructibility of functions
• Towards separating nondeterminism from determinism
• Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time
• scientific article; zbMATH DE number 17549
• Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines

This page was built for publication: A note on square rooting of time functions of Turing machines

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1405791)