If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?
-
29-09-2020 - |
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?
Solution
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.