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

Question

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?

Answer 1

You need to decide whether you want to talk in terms of decision problems (dealing with classes like $\textrm{P}$ or $\textrm{NP}$) or with function problems (dealing with classes like $\textrm{FP}$ or $\textrm{FNP}$).

If you choose to talk in terms of decision problems, then the decision problem is to decide, given $(m, n)$, whether it is true that $m = 2^n$. This problem can indeed be solved (and thus verified) in polynomial time.

If you choose to talk in terms of function problems, then the problem is given $n$, compute $2^n$. This cannot be done in polynomial time, even with non-determinism, but just because the output is exponentially big with respect to the input. Verification has nothing to do here.