# I have a decision problem with $2^n$ bit sized certificates, how would I verify my decision problem efficiently if it is in $NP$?

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!

## Question

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?

• What do you call the solution? – Dmitry Jul 16 '20 at 2:57
• @Dmitry Simple, the sum $2^k$+$M$ – Travis Wells Jul 16 '20 at 2:58
• @Dmitry It takes $2^n$ digits to calculate thus $2^n$ space. The reasons why, I think it takes $2^n$ space and time. – Travis Wells Jul 16 '20 at 3:01
• 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? – Dmitry Jul 16 '20 at 3:03
• @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. – Travis Wells Jul 16 '20 at 3:06

• 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. – Travis Wells Jul 19 '20 at 22:11
• I did edit my question after I found out about the $PSPACE$ algorithm and I still accept your answer to my question. – Travis Wells Jul 19 '20 at 22:18