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?