4
$\begingroup$

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?

Some comments:

  • 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$.

  • This is related to another question of mine.

Improve this question
$\endgroup$
12
  • 2
    $\begingroup$ (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. $\endgroup$
    – Neal Young
    Commented Sep 2, 2020 at 1:10
  • 7
    $\begingroup$ 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$). $\endgroup$
    – Emil Jeřábek
    Commented Sep 2, 2020 at 6:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – The T
    Commented Sep 2, 2020 at 15:42
  • 1
    $\begingroup$ A positive answer here would in particular falsify the more general “no formula for primes” conjecture here: cstheory.stackexchange.com/questions/46902/…, and least given a modest extra assumption. $\endgroup$
    – Geoffrey Irving
    Commented Sep 3, 2020 at 14:47
  • 1
    $\begingroup$ Of course you can it in polynomial time in the number of bits of the prime, but this is too slow to resolve either of our questions. $\endgroup$
    – Geoffrey Irving
    Commented Sep 4, 2020 at 7:32

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.