Tape bounds for time-bounded turing machines

作者：

Highlights：

•

摘要

Let L be a language recognized by a nondeterministic (single-tape) Turing machine of time complexity T(n)≥n2. Then L is also recognized by a deterministic (single-tape) Turing machine of tape complexity T1/2(n).

论文关键词：

论文评审过程：Received 30 April 1971, Available online 27 December 2007.

论文官网地址：https://doi.org/10.1016/S0022-0000(72)80017-5