I have been working on a problem for days, that I previously mentioned on ComScience StackExchange. The answers were helpful. But, I need more information to develop a polynomial space algorithm.

I would like to know if any researchers have found an efficient method to solve this problem.

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

I was told it was in $NP$ which means it is in $NPSPACE$. Since $PSPACE$=$NPSPACE$ a deterministic polynomial space algorithm exists for this problem.

It would be mathematically interesting to see how you would circumvent calculating $2^k$ because the value $2^k$ has $2^n$ bits and digits. So something fancy must be done to circumvent that problem.

## Question

I am just an amateur seeking a real mathematician's opinion and advice into what areas of research I should look into for developing this algorithm. Perhaps seeking references or papers into what I have found could turn out to be useful. May, I ask on the main site?