# I can verify solutions to my problem in polynomial time, how would a non-deterministic algorithm arrive to a solution if it always takes $2^n$ bits?

Decision Problem: Given integers as inputs for $$K$$ and $$M$$. Is the sum of $$2^k$$ + $$M$$ a $$prime$$?

## Verifier

m = int(input('Enter integer for M: '))
sum_of_2**K+M=int(input('enter the sum of 2^k+m: '))

if AKS.sum_of_2**K+M == True:

# Powers of 2 can be verified in O(N) time
# make sure there is all 0-bits after the 1st ONE-bit

# Use difference to verify problem

if sum_of_2**K+M - (M) is a power_of_2:
OUTPUT Solution Verified

The powers of 2 have approximately $$2^n$$ digits. Consider $$2^k$$ where $$K$$ = 100000. Compare the amount of digits in $$K$$ to the amount of digits in it's solution! Also take note that the powers of 2 have $$2^n$$ bits as its 0-bit Unary essentially for the exponent $$n$$.

## Question

How would a non-deterministic machine solve this problem in polynomial time?

• The complexity of AKS is $$O(log(N)^6)$$ where N is the input number. In your case the complexity would be $$O(K^6)$$. Try editing the post and explain “what exactly is the input to the problem?”. As for you question about NTM, in general, if you already have polynomial verifier without any witness or certificate, then the verifier is actually the deterministic algorithm. Hence, the same algo will work for NTM. Commented Jul 17, 2020 at 7:32
• I think that the point of the asker is that the number $k$ in the input is encoded as binary, and thus representing the number $2^k + M$ requires an exponential number of bits compared to the size of the input. Commented Jul 17, 2020 at 7:56
• @TravisWells, didn't you post s very similar question to this recently? What happened to that question? Commented Jul 17, 2020 at 8:17
• @prime_hit How would an NTM arrive at the answer that has 2^n bits in polytime? When the only inputs are $K$ and $M$? Commented Jul 17, 2020 at 19:20
• @TravisWells It depends if the input $K$ is in binary or unary. If it is in unary, then this is definitely solvable in polynomial time. $2^K$ requires $K$ bits and AKS can decide the primality of $2^K$ in $O(K^6)$ time. If $K$ is in binary, then I don’t think we can do this in polytime w.r.t this form of input. Note that complexity class depends on the format of input. Commented Jul 17, 2020 at 19:27

• Yes, the verifier is polynomial. But the decision problem requires calculating 2^k. Which takes $2^n$ time. How would an $NP$ machine will "know" a yes or no instance? To circumvent the hassle of using 2^n time? Commented Jul 17, 2020 at 19:16
• How? It takes $2^n$ space to store the bits. The verifier would require input with $2^n$ bits no matter what. The Turing machine (non-deterministic) is taking $K$ and $M$ as inputs. Commented Jul 17, 2020 at 19:17
• Its more than that because the problem is already known in to be in $EXP$. It has not been proven that no NP (polynomial) algorithim exists. Perhaps there is a clever way to get "yes" or "no". Commented Jul 17, 2020 at 19:52