# 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. Jul 17 '20 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. Jul 17 '20 at 7:56
• @TravisWells, didn't you post s very similar question to this recently? What happened to that question? Jul 17 '20 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$? Jul 17 '20 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. Jul 17 '20 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? Jul 17 '20 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. Jul 17 '20 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". Jul 17 '20 at 19:52