Decision Problem: Is $2^k$ + $M$ a prime?

The inputs for both $K$ and $M$ are integers only. The solution is the sum of $2^k$+$M$. (Use AKS to decide prime)

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!


Seeing that the decision problem's certificate can be $2^n$ sized, how would I verify the decision problem in polynomial time, considering that I can just look at the transition states as a certificate in itself?

In other words, what would a polynomial time verifier look like for this decision problem?

  • $\begingroup$ What do you call the solution? $\endgroup$ – Dmitry Jul 16 '20 at 2:57
  • $\begingroup$ @Dmitry Simple, the sum $2^k$+$M$ $\endgroup$ – Travis Wells Jul 16 '20 at 2:58
  • $\begingroup$ @Dmitry It takes $2^n$ digits to calculate thus $2^n$ space. The reasons why, I think it takes $2^n$ space and time. $\endgroup$ – Travis Wells Jul 16 '20 at 3:01
  • 1
    $\begingroup$ You use very strange terminology. Why do you call this thing a solution? Depending on the algorithm, it doesn't even necessarily appear at any step (e.g. you don't need this for checking if $2^K$ is prime). I'm asking because this question doesn't make sense in general: Could the solution be verified in polynomial time even though the solution is exponentially large? Also, are you asking this question in general or only about this problem? $\endgroup$ – Dmitry Jul 16 '20 at 3:03
  • $\begingroup$ @Dmitry I think outside the box, and I have trouble seeing how a non-deterministic machine would arrive to a solution that has $2^n$ digits in polytime. That's impossible. Unless it was some sort of oracle that always knows yes or no. But, that doesn't tell me anything interesting. $\endgroup$ – Travis Wells Jul 16 '20 at 3:06

A decision problem has a yes/no answer, so it can't have "exponential size". You are asking about search problems, those can certainly have exponential size. And yes, if the size of the solution (written down in some suitably compact format, that is) is exponential in the size of the original problem, it is clearly impossible to even write down the answer in polynomial time.

In any case, P and NP strictly apply only to decision problems. But take a look at Belare's "Decision vs Search" for a relation between both.

  • $\begingroup$ The certificates are definitely exponential. $\endgroup$ – Travis Wells Jul 18 '20 at 19:03
  • $\begingroup$ I'm not sure why no one realizes the above sentence. $\endgroup$ – Travis Wells Jul 18 '20 at 19:13
  • $\begingroup$ @TravisWells, that some certificate is of exponential size doesn't mean all are, there could be very short ones too. $\endgroup$ – vonbrand Jul 19 '20 at 12:29
  • $\begingroup$ Seems like I can just look transitions in a NTM and consider that as a certificate. If it is $NP$. It is $NPSPACE$. Since, $PSPACE$ = $NPSPACE$. I have proven a deterministic polynomial-space algorithm for this decision problem. Something equally clever as AKS I imagine. $\endgroup$ – Travis Wells Jul 19 '20 at 22:11
  • $\begingroup$ I did edit my question after I found out about the $PSPACE$ algorithm and I still accept your answer to my question. $\endgroup$ – Travis Wells Jul 19 '20 at 22:18

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.