I am having trouble with the statement that $DSPACE(\log^2n)\subseteq DTIME(n^{\log n})$ holds which is given without argument in the paper The structure and complexity of minimal NFA's over a unary alphabet in the proof of Theorem 3.2.

I only get to something like $DSPACE(\log^2n)\subseteq DTIME(\log n)$. (Using the usual line of arguments to count configurations as given in the answer to this related question.

In the paper above it is also mentioned in the same abstract that a TM transducer with operating with space in $O(\log^2 n)$ produces an output of length $O(n^{\log n})$. This too, I can not follow. Assuming an input tape of length $n$, a working tape of length $\log^2 n$, $|Q|$ states, and $|\Sigma|$ symbols; I count a total of:

  • $n*\log^2 n$ positions the TM can be in,
  • $|Q|$ states to be in (constant for this examination)
  • $|\Sigma|^{\log^2 n}$ working tape configurations. Resulting in a total of $n*\log^2 n*|Q|*||\Sigma|^{\log^2 n}$ configurations the transducer can be in . This gives me $O(n\log^2 n\log n)$ as an upper bound for the output length of a transducer with $O(\log^2 n)$ space. The paper however claims $O(n^{\log n})$.

I am confused. Please help me understand why. Thanks!

EDIT: It seems my confusion might simply be a result of me thinking $\log^2 n = \log\log n$ ... but what is meant is $\log^2 n = (\log n)^2$? o.O


1 Answer 1


My experience is that $\log^2 n$ normally means $(\log n)^2$, unless context indicates otherwise.

The result follows from the fact that $DSPACE(f(n)) \subseteq DTIME(2^{f(n)})$ (proven by using the fact that if a deterministic algorithm repeats the same state twice, then it loops infinitely).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.