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

• won't the answer have O(n) digits? exactly n binary digits? – Kevin Wang May 22 '20 at 23:45
• @KevinWang When $n$ is some exponent for the function-problem the answer would be both exponential in the value and the length of $n$. Take $2$^$1000$ with 4 digits as its input-length. The answer would be exponentially larger $1071508607186267320948425049060001810561404811705533607443750388370351..............$ – Dingle Berry May 23 '20 at 1:08
• @KevinWang 2^n has exactly n 0-bits in the value, but not the input-length. – Dingle Berry May 23 '20 at 1:10

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.
• I guess I must induce that verification does not necessarily mean that it is solvable in $NP$-time. – Dingle Berry May 24 '20 at 4:12
• Wait.. Unary Subset Sum is in $P$, with the function of the input length its exponential, isn't it? Why not here? Hmm... – Dingle Berry Jun 20 '20 at 22:46