Suppose, I wanted to verify the solution to $2$^$3$. Which is $8$.
The $powers~of~2$ have only one 1-bit at the start of the binary-string.
Verify Solution Efficently
n = 8 N = 3 IF only ONE 1-bit at start of binary-string: IF total_0-bits == N: if n is a power_of_2: OUTPUT solution verified, 2^3 == 8
A solution will always be approximately $2$^$N$ digits. Its not possible for even a non-deterministic machine to arrive to a solution with $2$^$N$ digits faster than $2$^$N$ time.
Can this problem be solved efficently in non-deterministic poly-time? Why not if the solutions can be verified efficently?