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.

  • 4
    $\begingroup$ Shouldn't it simply be replacing $n$ with $\log n$ in the definition of EXPTIME, which gives this result? $\endgroup$
    – Dmitry
    Nov 30 '21 at 11:42
  • $\begingroup$ 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. $\endgroup$
    – Aldo
    Dec 1 '21 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.