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?