Can this language be decided in polynomial time?

Question

Let $L=${$0^{2^n}|n>=0$} Can this be decided in polynomial time?
I can decide it in non polynomial time, by going over all '0's and delete 2 of them from the beginning and the end of the string, but can this be done in polynomial time as well?

Answer 1

It can be done in polynomial time. Because you should read all the $0$'s at least one time. In general if a string has length $m$ than time of decision process is $\Omega(m)$