Given arbitrary integers of $K$ and $M$, can deciding $2^K$ + $M$ is a prime be in $P$? 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?
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.