# 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? Commented May 22, 2020 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..............$ Commented May 23, 2020 at 1:08
• @KevinWang 2^n has exactly n 0-bits in the value, but not the input-length. Commented May 23, 2020 at 1:10

## 1 Answer

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. Commented May 24, 2020 at 4:12
• What do you mean? The ability to verify solutions of a problem in polynomial time is exactly the same as being able to solve the problem in non-deterministic polynomial time. If you can verify a solution, then you can non-deterministically guess it and then verify, which allows for a solution in NP. The problem with your question is that it is not precise enough. When you say "Can this problem be solved efficently in non-deterministic poly-time?" do you mean the decision problem or the function problem? Both are described in my answer. including the response for each case. Commented May 24, 2020 at 4:54
• The function problem. Calculating 2^n will always 2^n time. But, its solutions can be verified in poly-time. Commented May 24, 2020 at 16:44
• In poly time with respect to the solution itself, but that solution is exponentially long with respect to the input. When people say that NP is the class of problems that can be verified efficiently, they mean as a function of the input length, not the solution length. That's why it is a requirement to have polynomially long solutions. Commented May 24, 2020 at 20:58
• Wait.. Unary Subset Sum is in $P$, with the function of the input length its exponential, isn't it? Why not here? Hmm... Commented Jun 20, 2020 at 22:46