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

Question

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?

Answer 1

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.