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.


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?

| |
  • $\begingroup$ Perhaps consider asking at Theoretical Computer Science. $\endgroup$ – Joel Reyes Noche Jul 22 at 2:36
  • 1
    $\begingroup$ Before you ask this here, it would be helpful to motivate the desire for a PSPACE algorithm. In particular, it is hard to imagine how compressible large factors would be. Do you need to know the prime factors if there are any? This would fly better on MathOverflow as a reference request for PSPACE algorithms in computational number theory. Before you ask that version, do a web search and see what you can find on your own, and then ask if such references you found would be worth reading for this problem. Gerhard "Trying To Save Some Space" Paseman, 2020.07.21. $\endgroup$ – Gerhard Paseman Jul 22 at 3:08
  • $\begingroup$ @GerhardPaseman nice one with that signature ;-) $\endgroup$ – David Roberts Jul 22 at 4:50
  • 2
    $\begingroup$ "the value $2^k$ has $2^n$ bits and digits." Not following. What's $n$? $2^k$ has $k+1$ bits, and roughly $(0.3)k$ digits. $\endgroup$ – Gerry Myerson Jul 22 at 5:26
  • 1
    $\begingroup$ Do you have a reason why this problem would be in NP? $\endgroup$ – S. Carnahan Jul 22 at 6:28
  • $\begingroup$ @GerryMyerson In computer Science we go by the input length. Consider the powers of 2 have EXACTLY value N 0-bits. Consider reducing binary subset sum into 0-bit Tally SubsetSum. Tally Subset Sum is in P. The reduction is exponential otherwise P=NP. $\endgroup$ – Travis Wells Jul 22 at 11:06
  • $\begingroup$ @S.Carnahan I was told the execution paths can be used as a certificate for proving it is in NP. $\endgroup$ – Travis Wells Jul 22 at 11:07
  • 2
    $\begingroup$ "In computer Science we go by the input length." The input length of $2^k$ is $k+1$. "Consider the powers of 2 have EXACTLY value N 0-bits." Every single power of two has the same number of 0-bits, namely, $N$? I asked you "What's $n$," and instead of answering me you introduce "$N$" with no explanation. In "computer Science", you go by input length; in Mathematics, we go by defining our terms, and making sense. $\endgroup$ – Gerry Myerson Jul 22 at 11:16
  • 2
    $\begingroup$ Good. The input length of $2^N$ is $N+1$. The input length of $2^K$ is $K+1$. And the input length of $2^k$ is $k+1$. That should cover all the bases. Do you still stand by "the value $2^k$ has $2^n$ bits and digits"? $\endgroup$ – Gerry Myerson Jul 22 at 12:18
  • 1
    $\begingroup$ The OP has given no indication that he (pronoun presumption) knows the notation or the conventions here in MathOverflow, and seems to be using an unstated convention from computer science. You can try to force him to follow the convention of this forum through your commenting style, or you can say something like "What you say does not make sense to me unless n is log k. Even then more exposition is needed. In this forum we need things to be more clear and explicit." Gerhard "These Times Affect Us All" Paseman, 2020.07.22. $\endgroup$ – Gerhard Paseman Jul 22 at 23:21
  • 2
    $\begingroup$ @TravisWells why do you have $K$ and $n$ and $k$—are these all potentially different numbers? What is the definition of the numbers $n$ and $k$, in terms of the given $M$ and $K$? The question as it stands is definitely not suitable for the main site because you haven't defined or unambiguously described half the variables you have introduced. $\endgroup$ – David Roberts Jul 23 at 4:28
  • 1
    $\begingroup$ @Gerhard I'm glad that your commenting style has elicited the response, "in the binary length the value $2^K$ is exponential." I hope you will continue to extract more exposition, clarity, and explicitness from OP. $\endgroup$ – Gerry Myerson Jul 23 at 6:48
  • 2
    $\begingroup$ I note that the m.se question to which OP links was closed by the voters there because it was not at all clear what OP was asking. How is an unclear question there going to clarify an unclear question here? $\endgroup$ – Gerry Myerson Jul 23 at 6:52
  • 1
    $\begingroup$ Let me try another approach. You've said nothing about any actual primality-testing algorithm. Your whole question is based on the problem of calculating $2^k$. So, doesn't your argument suggest that multiplying two numbers of the form $2^k+m$ can't be done in polynomial space? Or dividing $2^k+m$ by three? The way I see it: if your argument really suggests you can't multiply, or divide by three, in polynomial space, then it shows that you don't understand what polynomial space is. And if it doesn't show that you can't do those things in polynomial space, then (continued) $\endgroup$ – Gerry Myerson Jul 23 at 13:08
  • 1
    $\begingroup$ (continued) then it behooves you to explain what part of your argument applies to primality-testing but not to multiplication and not to division by three, because you haven't used any facts about primality-testing in your question. $\endgroup$ – Gerry Myerson Jul 23 at 13:10

You must log in to answer this question.

Browse other questions tagged .