Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$?

Question

Given arbitrary integers of $K$ and $M$, is $2^K$ + $M$ a prime?

K = int(input('enter exponent K: '))
M = int(input('enter integer for M: '))

if AKS.Primality(2**K + M) == True:
    OUTPUT 'yes'
else:
    OUTPUT 'no'

I am not knowledgeable enough in number theory or any other field of mathematics to know the answer to this question.

Question

Is there a polynomial-time algorithm for this decision problem?

Answer 1

Assuming you mean "polynomial in the size of the binary representation of K and M", 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.