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.


Can this problem be solved efficently in non-deterministic poly-time? Why not if the solutions can be verified efficently?

  • $\begingroup$ won't the answer have O(n) digits? exactly n binary digits? $\endgroup$ – Kevin Wang May 22 '20 at 23:45
  • $\begingroup$ @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..............$ $\endgroup$ – Dingle Berry May 23 '20 at 1:08
  • $\begingroup$ @KevinWang 2^n has exactly n 0-bits in the value, but not the input-length. $\endgroup$ – 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.

  • $\begingroup$ I guess I must induce that verification does not necessarily mean that it is solvable in $NP$-time. $\endgroup$ – Dingle Berry May 24 '20 at 4:12
  • $\begingroup$ 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. $\endgroup$ – Bernardo Subercaseaux May 24 '20 at 4:54
  • $\begingroup$ The function problem. Calculating 2^n will always 2^n time. But, its solutions can be verified in poly-time. $\endgroup$ – Dingle Berry May 24 '20 at 16:44
  • $\begingroup$ 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. $\endgroup$ – Bernardo Subercaseaux May 24 '20 at 20:58
  • $\begingroup$ Wait.. Unary Subset Sum is in $P$, with the function of the input length its exponential, isn't it? Why not here? Hmm... $\endgroup$ – Dingle Berry Jun 20 '20 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.