0
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ 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. $\endgroup$
    – prime_hit
    Commented Jul 17, 2020 at 7:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Laakeri
    Commented Jul 17, 2020 at 7:56
  • 1
    $\begingroup$ @TravisWells, didn't you post s very similar question to this recently? What happened to that question? $\endgroup$
    – Aaron Rotenberg
    Commented Jul 17, 2020 at 8:17
  • $\begingroup$ @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$? $\endgroup$
    – The T
    Commented Jul 17, 2020 at 19:20
  • 1
    $\begingroup$ @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. $\endgroup$
    – prime_hit
    Commented Jul 17, 2020 at 19:27

2 Answers 2

Reset to default
1
$\begingroup$

The verifier is polynomial in K and M. It’s even polynomial in K and the size of M. But that’s not what we count as “in P”. It would have to be polynomial in the size of K and the size of M. If K = 100,000 then the size of K is just 17 bits. It is highly unlikely that any algorithm can check primality in polynomial time in this number - not even if M=-1 where we have a much faster polynomial in K algorithm.

It’s not proven to be impossible but very very unlikely. Even if I gave you a 50,000 bit divisor of your 100,000 bit number, you couldn’t verify that quickly enough.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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? $\endgroup$
    – The T
    Commented Jul 17, 2020 at 19:16
1
$\begingroup$

As I see it, this decision problem is obviously in P. Therefore, there is nothing for non-deterministic Turing machine to guess. Non-deterministic Turing machine would call polynomial-time verifier for a given problem instance and the problem would be solved in polynomial time.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – The T
    Commented Jul 17, 2020 at 19:17
  • $\begingroup$ It seems that I misunderstood. In that case, the problem does not admit polynomial-time verifier and NDTM cannot solve it in polynomial time. $\endgroup$
    – dumpram
    Commented Jul 17, 2020 at 19:40
  • $\begingroup$ 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". $\endgroup$
    – The T
    Commented Jul 17, 2020 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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