# From binary to unary and EXPTIME

I read in [Razborov, "An equivalence between...", p.248] that

It is well recognized in Theoretical Computer Science that when we change the representation of integers from binary to unary, the class $$\mathsf{EXPTIME}$$ becomes not the class $$\mathsf{P}$$ but the class $$\mathsf{TIME}\left(2^{(\log n)^{O(1)}}\right)$$.

Unfortunatly there is no reference to this well recognized fact. I would like to get a proof of it or a reference. Thanks.

• Shouldn't it simply be replacing $n$ with $\log n$ in the definition of EXPTIME, which gives this result? Nov 30 '21 at 11:42
• I think you are right. If we denote by N the input length in unary and by n the input length in binary then it should be n = O(log N). Every algorithm that takes 2^(n^c) takes 2^(log N)^(O(1)) when expressed as a function of the unary input length.
– Aldo
Dec 1 '21 at 10:39