4

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.

Travis Wells
  • 149
  • 6
  • 2
    (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. – Neal Young Sep 02 '20 at 01:10
  • The notation seems to be switching randomly. Is $k=K$ and $m=M$? – Emil Jeřábek Sep 02 '20 at 06:14
  • 7
    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$). – Emil Jeřábek Sep 02 '20 at 06:17
  • @EmilJeřábek An idea: Can we show its in $NP$, because $PSPACE$ = $NPSPACE$? That would non-constructively prove that an algorithm exists. – Travis Wells Sep 02 '20 at 06:34
  • 1
    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. – Travis Wells Sep 02 '20 at 15:42
  • 1
    A positive answer here would in particular falsify the more general “no formula for primes” conjecture here: https://cstheory.stackexchange.com/questions/46902/formalizing-the-no-formula-for-primes-intuition, and least given a modest extra assumption. – Geoffrey Irving Sep 03 '20 at 14:47
  • @GeoffreyIrving I found out how to generate all possible expressions of $2^k$+$m$ given that I use a solution as input. (eg. solution = 5, output expression $2^0$ + $4$ = $5$, $2^1$ + $ 3$ = $5$) I am fairly new to ComputerScience, but wouldn't that mean a "turing machine" can recognize the "language" in polytime? – Travis Wells Sep 03 '20 at 18:27
  • @Travis: The hard part, of course, is recognizing which are prime. – Geoffrey Irving Sep 03 '20 at 19:37
  • @GeoffreyIrving We have AKS primality, which is poly-time. All the solutions are prime numbers and can be recognized in poly-time. After the primality, we then find the expressions. Although, probabilistic tests are more practical. – Travis Wells Sep 03 '20 at 22:26
  • @GeoffreyIrving Not hard at all.https://pastebin.com/qCcfnSRG – Travis Wells Sep 03 '20 at 23:14
  • 1
    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. – Geoffrey Irving Sep 04 '20 at 07:32
  • you may want to look at this post.
    https://math.stackexchange.com/questions/3810222/primality-test-for-specific-class-of-n-k-cdot-2n1     – user25406 Sep 04 '20 at 14:41

0 Answers0