A Note Concerning Nondeterministic Tape Complexities
Óscar H. Ibarra · Journal of the ACM · 1972
A set of sufficient conditions on tape functions Ll(n) and L2(n) is presented that guarantees the existence of a set accepted by an Ll(n)-tape bounded nondeterministic Turing machine, but not accepted by any L~(n)-tape bounded nondeterministic Turing machine.Interesting corollaries arise.For example, it is shown that, for integers m >_ 0, p > 1, and q > 1, there is a set accepted by an [n~+(P/q)]-tape bounded nondeterministic Turing machine that is not accepted by any [nm+(p/(q+l))]-tape bounded nondeterministic Turing machine.