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.

**Question**

*Can this problem be solved efficently in non-deterministic poly-time? Why not if the solutions can be verified efficently?*