If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?


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?