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!
Could the solution be verified in polynomial time even though the solution is exponentially large?
If no, can I say it is not in $ NP$ ?