# 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?