# If a decision problem’s solution is exponentially large, then is it impossible for it to be 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

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$$?