# Deciding whether $2^k+m$ is prime

I thought something fancy can be done with number-theory or memoization, but neither worked for me. Being limited in knowledge I decided to ask experts.

Does there exist a deterministic polynomial-space algorithm for the following decision problem?

Instance: Two positive integers $$k$$ and $$m$$ in decimal representation.
Question: Is $$2^k+m$$ a prime number?

• By polynomial-space I mean that the space complexity of the algorithm should be bounded by a polynomial in the input length $$\log k+\log m$$.
• The naive approach to this problem determines the decimal representation of $$2^k+m$$ and then applies a fast primality testing algorithm. It is easy to see that this naive approach requires exponential space, just for writing down the decimal representation of $$2^k+m$$.
• (i) By "polynomial space" do you mean polynomial in the size of the (presumably binary) encoding of $K$ and $M$? That is, polynomial in $\log K + \log M$? (ii) "Calculating $k\mapsto 2^k$ takes exponential time" is a strange thing to say. Do you just mean representing $2^k$ takes space exponential in $\log k$? That's sort of obvious, I think, so doesn't help clarify your post or why it is interesting (my opinion). And the post you link to, and its answers, reflect a similar confusion. But I think the question you ask is interesting. Editing the post to clarify it would help. Commented Sep 2, 2020 at 1:10
• Anyway, as far as I am aware, no such algorithm is known even in the special case of Fermat primes ($M=1$, $K$ a power of $2$). Commented Sep 2, 2020 at 6:17
• All problems in $NP$ are in $PSPACE$, just by showing its in $NP$ is enough to prove a deterministic poly-space algorithm exists. Whether one is known is apparently open. Commented Sep 2, 2020 at 15:42