<p>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.</p>
<p><em>Does there exist a deterministic polynomial-space algorithm
for the following decision problem?</em></p>
<blockquote>
<p><strong>Instance:</strong> Two positive integers <span class="math-container">$k$</span> and <span class="math-container">$m$</span> in decimal representation.<br />
<strong>Question:</strong> Is <span class="math-container">$2^k+m$</span> a prime number?</p>
</blockquote>
<p>Some comments:</p>
<ul>
<li><p>By polynomial-space I mean that the space complexity of the algorithm should be bounded by a polynomial in the input length <span class="math-container">$\log k+\log m$</span>.</p>
</li>
<li><p>The naive approach to this problem determines the decimal representation of <span class="math-container">$2^k+m$</span> 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 <span class="math-container">$2^k+m$</span>.</p>
</li>
<li><p>This is related to another <a href="https://math.stackexchange.com/a/3563818/602057">question of mine</a>.</p>
</li>
</ul>

CC BY-SA 4.0
2020-09-02T01:10:35.140Z
(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
CC BY-SA 4.0
2020-09-02T06:14:53.320Z
The notation seems to be switching randomly. Is $k=K$ and $m=M$?
Emil Jeřábek
CC BY-SA 4.0
2020-09-02T06:17:03.163Z
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
CC BY-SA 4.0
2020-09-02T06:34:25.447Z
@EmilJeřábek An idea: Can we show its in $NP$, because $PSPACE$ = $NPSPACE$? That would non-constructively prove that an algorithm exists.
The T
CC BY-SA 4.0
2020-09-02T15:42:44.677Z
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.
The T
CC BY-SA 4.0
2020-09-03T14:47:10.417Z
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
CC BY-SA 4.0
2020-09-03T18:27:29.007Z
@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?
The T
CC BY-SA 4.0
2020-09-03T19:37:50.093Z
@Travis: The hard part, of course, is recognizing which are prime.
Geoffrey Irving
CC BY-SA 4.0
2020-09-03T22:26:18.250Z
@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.
The T
CC BY-SA 4.0
2020-09-03T23:14:13.323Z
@GeoffreyIrving Not hard at all.https://pastebin.com/qCcfnSRG
The T
CC BY-SA 4.0
2020-09-04T07:32:43.913Z
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
CC BY-SA 4.0
2020-09-04T14:41:03.763Z
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
<ds.algorithms><pspace>
Deciding whether $2^k+m$ is prime
The T
# Deciding whether $2^k+m$ is prime

(Asked by: username_0 on 2020-09-01)

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](https://math.stackexchange.com/a/3563818/602057).

**Tags:** ds.algorithms, pspace

> **Comments:**
> **username_1**: (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.  
> **username_2**: The notation seems to be switching randomly. Is $k=K$ and $m=M$?  
> **username_2**: 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$).  
> **username_0**: @EmilJeřábek An idea: Can we show its in $NP$, because $PSPACE$ = $NPSPACE$? That would non-constructively prove that an algorithm exists.  
> **username_0**: 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.  
> **username_3**: 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.  
> **username_0**: @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?  
> **username_3**: @Travis: The hard part, of course, is recognizing which are prime.  
> **username_0**: @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.  
> **username_0**: @GeoffreyIrving Not hard at all.https://pastebin.com/qCcfnSRG  
> **username_3**: 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.  
> **username_4**: you may want to look at this post.   https://math.stackexchange.com/questions/3810222/primality-test-for-specific-class-of-n-k-cdot-2n1  

---

## 0 answers

