Question $1$: Time constructible functions.

The following theorem that relates the class of regular languages and the

time complexity classes was proved by Kojiro Kobayashi.

Theorem $1.[1]$ If $f(n)=o(nlogn)$ then DTIME$(f(n))subeREG.$

Clearly, the theorem is most interesting when applied on functions $f(n)=$

$(n).$ Indeed, if $f(n)=o(n)$ then a machine with time complexity $f(n)$ has

no time to even read the entire input. In that case, the machine only exam$-$

ines a bounded part of the tape, and then it is not very difficult to see that

the machine recognizes a regular language ${?}^1.$

Explain why REG subeDTIME$(n)$ and conclude from Theorem $1$ that

DTIME$(n)=$ REG.

Use Theorem $1$ to show that $f(n)=n$ is not time constructible. That

is$,$ there is no TM $M$ that runs in $O(n)$ time and on input $1^n$ halts

with the binary representation of $n$ written on the tape.

Hint: Consider the following language.

$L=\{1^n$:$nis$ a power $of2\}$

Prove that $L!$inREG$=$DTIME$(n).$ Then, assume towards con$-$

tradiction that $f(n)=n$ is time constructible and show that then

LinDTIME$(n).$

${?}^1$ In fact, if $M$ is a TM with running time $t_M$ such that for some $n_{0}1,$

then $t_M(n)is$ eventually constant and hence $L(M)inDTIME(O(1)).Itis$ not hard $to$ see

that LinDTIME$(O(1))$ iff Thus, LinDTIME$(o(n))$ iff $Lis$

finite $or$ cofinite $(whichis$ even weaker than being regular$).$