Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$?
Assuming you mean &quot;polynomial in the size of the binary representation of K and M&quot;, then it is extremely unlikely, but proving that it is impossible will also be very difficult.
There are polynomial time algorithms for checking primality, but they would be applied to a number whose size is K, which is a lot bigger than checking a number whose size is the same as the size of K.