A Note Concerning Nondeterministic Tape Complexities

This is the authors' abstract. We don't add key points for this paper.

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.