I think so, in positional notation. That's what I was alluding to with my O(log log k) comment. But there is no polynomial time algorithm to reduce 2^n to a tally number (obviously).

I once read something by Nelson about the polynomial hierarchy in complexity theory, but I can't find it now.