<p>There are no known NP-complete problems whose input would consist of primes <sub>(or, say, <span class="math-container">$k$</span>-tuples of primes, or even more complicated structures as long as they contain at least one prime of length <span class="math-container">$\ge n^\epsilon$</span>, where <span class="math-container">$n$</span> is the total length of the input, and <span class="math-container">$\epsilon&gt;0$</span> is a constant).</sub></p>
<p>The existence of such problems (even completely artificial) would require better deterministic prime generators than what is currently known. Specifically:</p>
<blockquote>
<p><strong>Observation:</strong></p>
<ol>
<li><p>If there are polynomial-time functions <span class="math-container">$f,g$</span> such that <span class="math-container">$g(f(w))=w$</span> for all <span class="math-container">$w\in\{0,1\}^*$</span> (which implies <span class="math-container">$f$</span> is injective), and the output of <span class="math-container">$f$</span> consists entirely of primes, then there exist NP-complete languages whose inputs are primes.</p>
</li>
<li><p>Assuming the <a href="https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture" rel="noreferrer">Berman–Hartmanis conjecture</a>, the converse also holds.</p>
</li>
</ol>
</blockquote>
<p><strong>Proof:</strong></p>
<p><span class="math-container">$1\to2$</span>: Fix any NP-complete language <span class="math-container">$L$</span>. Then the language <span class="math-container">$L'=\{x\text{ prime}:g(x)\in L\}$</span> is in NP as it reduces to <span class="math-container">$L$</span> via <span class="math-container">$g$</span>, and it is NP-hard as <span class="math-container">$L$</span> reduces to it via <span class="math-container">$f$</span>.</p>
<p><span class="math-container">$2\to1$</span>: Let <span class="math-container">$L$</span> be an NP-complete language on primes. We can consider it as a language on arbitrary inputs such that all non-primes are rejected. Assuming the Berman–Hartmanis conjecture, <span class="math-container">$L$</span> is paddable: there is a poly-time function <span class="math-container">$h(x,w)$</span> with a poly-time left inverse <span class="math-container">$h'(z)$</span> such that <span class="math-container">$x\in L\iff h(x,w)\in L$</span>. Fix a prime <span class="math-container">$p\in L$</span>.  Then the requirements hold for the functions <span class="math-container">$f(w)=h(p,w)$</span> and <span class="math-container">$g(z)={}$</span>the second element of the pair <span class="math-container">$h'(z)$</span>.</p>
<p><strong>Notes:</strong></p>
<ul>
<li><p>For specific NP-complete languages known so far, the conclusion of the Berman–Hartmanis conjecture is typically easy to show.</p>
</li>
<li><p>The implication <span class="math-container">$1\to2$</span> does not quite need the existence of a poly-time <span class="math-container">$g$</span>; it is enough to assume that <span class="math-container">$f$</span> is injective and <span class="math-container">$|f(w)|\ge|w|^\delta$</span> for some constant <span class="math-container">$\delta&gt;0$</span>.</p>
</li>
<li><p>A (necessarily sparse) language <span class="math-container">$L$</span> is <strong>P</strong>-<em>printable</em> if there exists a poly-time function <span class="math-container">$h$</span> such that <span class="math-container">$h(1^n)$</span> outputs the set <span class="math-container">$\{w\in L:|w|\le n\}$</span>. If there exists a function <span class="math-container">$f$</span> as above, then e.g. <span class="math-container">$\{f(1^n):n\in\mathbb N\}$</span> is a <strong>P</strong>-printable infinite set of primes. This is a much weaker requirement than the existence of an <span class="math-container">$f$</span> as in the Observation, nevertheless even the existence of a <strong>P</strong>-printable infinite set of primes is an open problem; see the discussion in <a href="https://arxiv.org/abs/2109.14764" rel="noreferrer">https://arxiv.org/abs/2109.14764</a> .</p>
</li>
<li><p>If you relax the question to allow NP languages on primes that are NP-hard under <em>randomized</em> poly-time reductions, then such languages <em>do</em> exist, as you can construct <span class="math-container">$f$</span> and <span class="math-container">$g$</span> as above where <span class="math-container">$f$</span> is randomized poly-time (and <span class="math-container">$g$</span> is still deterministic).</p>
<p>E.g., let <span class="math-container">$f(w)$</span> be a randomly chosen prime of length <span class="math-container">$|w'|^2$</span> whose binary expansion starts with <span class="math-container">$1w'$</span>, where <span class="math-container">$w'$</span> is a prefix-free encoding of <span class="math-container">$w$</span> (e.g., if <span class="math-container">$w=w_0\dots w_{n-1}$</span>, let <span class="math-container">$w'=1w_01w_1\dots1w_{n-1}0$</span>), and let <span class="math-container">$g(x)$</span> decode the prefix of <span class="math-container">$x$</span>.</p>
<p>This construction can be derandomized assuming <a href="https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture" rel="noreferrer">Cramér’s conjecture</a>.</p>
</li>
</ul>

CC BY-SA 4.0
2023-07-25T20:26:48.897Z
Thank you for your insightful and useful answer. I am actually curious as to the consequences of such a problem existing. Perhaps I will post that as another question, pending some further investigations into this matter.
EGME
CC BY-SA 4.0
2023-07-25T20:16:36.117Z
2023-07-26T11:10:26.347Z
2023-07-26T11:10:26.347Z
Emil Jeřábek
<p>I don't know if it has an official name, but this problem is NP-complete (actually it's a simple &quot;number theory&quot; reformulation of the exact cover by 3-sets problem):</p>
<p>Given a set of <span class="math-container">$3n$</span> triprime numbers; find if there is a square-free product of <span class="math-container">$n$</span> of them. The problem is NP-complete even if their factors are given in the input.</p>

CC BY-SA 4.0
2023-07-26T07:45:03.697Z
If you allow as an input a long list of small primes in this manner, then you can trivially encode any problem by “primes”: e.g., encode a string $w_1\dots w_n\in\{0,1\}^n$ by the list $(2+w_1,\dots,2+w_n)$. I don’t think this is what the OP had in mind.
Emil Jeřábek
CC BY-SA 4.0
2023-07-26T09:03:04.470Z
@EmilJeřábek: I agree, but the problem in my answer has an almost "natural" interpretation: a list of triprimes as input and asks for a square-free product. Up to my knowledge, I think it's the closest to what the OP asked, but let's see his opinion.
Marzio De Biasi
CC BY-SA 4.0
2023-07-26T14:47:37.660Z
@EmilJeřábek, Marzio. The problem might be here that you are measuring complexity relative to n (not even the binary length of n), rather than the binary length of the prime numbers themselves? Perhaps you could clarify this?
EGME
CC BY-SA 4.0
2023-07-26T15:01:14.367Z
@EGME Could *you* clarify what you mean by this? The definition of NP and NP-completeness is such that complexity is measured with respect to the total length of the input. Here, the length of the input is not quite the parameter denoted as $n$, but it is close: the input is a list of $9n$ primes, each of binary length $O(\log n)$ (this is not specified in the problem statement, but the reduction showing NP-completeness gives this). Thus, the length of the input, which is the *sum* of the lengths of the primes involved, is $O(n\log n)$, whereas the *individual* primes have length $O(\log n)$.
Emil Jeřábek
CC BY-SA 4.0
2023-07-26T15:23:52.033Z
We may assume triprime numbers with no square factors, then each triprime number is equivalent to a set of exactly three primes, and you are looking for n sets with no common element. Map the i-th prime to the number i, and it's the same problem with no primes involved.
gnasher729
CC BY-SA 4.0
2023-07-26T15:38:36.057Z
@EmilJeřábek. Thank, you, you have actually clarified it very nicely. The total input length is exponentially larger than the length of any of the primes. I am looking for a problem where you are working relative to the binary length of the primes themselves.  I guess I did not explain that clearly enough in the post.
EGME
CC BY-SA 4.0
2023-07-27T07:33:46.833Z
@EGME: then my answer is useless; if you allow randomization then you can artificially use larger primes (find a set of primes of binary length $O(n)$), but without randomization there are no known methods (see Emil's answer)
Marzio De Biasi
CC BY-SA 4.0
2023-07-26T07:28:15.020Z
2023-07-26T07:28:15.020Z
Marzio De Biasi
<p>Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are probably some, me just being an ignoramus.  Could you provide references?</p>

CC BY-SA 4.0
2023-07-25T18:30:38.557Z
You might find something here - https://en.wikipedia.org/wiki/List_of_NP-complete_problems.
if there is such a problem i doubt if its well-known.
Aditya Mishra
CC BY-SA 4.0
2023-07-26T04:58:48.773Z
For whatever reason this comes to my mind https://arxiv.org/abs/2109.14764
Tayfun Pay
CC BY-SA 4.0
2023-07-26T09:07:36.707Z
@TayfunPay Thanks for the link! I mentioned it in my answer.
Emil Jeřábek
CC BY-SA 4.0
2023-07-26T10:57:17.740Z
@TayfunPay. Thanks for pointing out that interesting article.
EGME
<reference-request><soft-question><np-complete><primes>
NP-complete problems where the inputs are prime numbers
EGME
# NP-complete problems where the inputs are prime numbers

(Asked by: username_0 on 2023-07-25)

Are there (well?) known NP-complete problems where the input(s) is(are) a(some) prime number(s), with complexity measured relative to the binary length of the input number(s)? I am thinking there are probably some, me just being an ignoramus. Could you provide references?

**Tags:** reference-request, soft-question, np-complete, primes
> **Comments:**
> **username_1**: You might find something here - https://en.wikipedia.org/wiki/List_of_NP-complete_problems. if there is such a problem i doubt if its well-known.  
> **username_2**: For whatever reason this comes to my mind https://arxiv.org/abs/2109.14764  
> **username_3**: @TayfunPay Thanks for the link! I mentioned it in my answer.  
> **username_0**: @TayfunPay. Thanks for pointing out that interesting article.  

---

## 2 answers

### Answer by username_3 on 2023-07-25. Score: 7

There are no known NP-complete problems whose input would consist of primes (or, say, $k$-tuples of primes, or even more complicated structures as long as they contain at least one prime of length $\ge n^\epsilon$, where $n$ is the total length of the input, and $\epsilon>0$ is a constant).

The existence of such problems (even completely artificial) would require better deterministic prime generators than what is currently known. Specifically:

> **Observation:**
>
> 1. If there are polynomial-time functions $f,g$ such that $g(f(w))=w$ for all $w\in\{0,1\}^\*$ (which implies $f$ is injective), and the output of $f$ consists entirely of primes, then there exist NP-complete languages whose inputs are primes.
> 2. Assuming the [Berman–Hartmanis conjecture](https://en.wikipedia.org/wiki/Berman%E2%80%93Hartmanis_conjecture), the converse also holds.

**Proof:**

$1\to2$: Fix any NP-complete language $L$. Then the language $L'=\{x\text{ prime}:g(x)\in L\}$ is in NP as it reduces to $L$ via $g$, and it is NP-hard as $L$ reduces to it via $f$.

$2\to1$: Let $L$ be an NP-complete language on primes. We can consider it as a language on arbitrary inputs such that all non-primes are rejected. Assuming the Berman–Hartmanis conjecture, $L$ is paddable: there is a poly-time function $h(x,w)$ with a poly-time left inverse $h'(z)$ such that $x\in L\iff h(x,w)\in L$. Fix a prime $p\in L$. Then the requirements hold for the functions $f(w)=h(p,w)$ and $g(z)={}$the second element of the pair $h'(z)$.

**Notes:**

* For specific NP-complete languages known so far, the conclusion of the Berman–Hartmanis conjecture is typically easy to show.
* The implication $1\to2$ does not quite need the existence of a poly-time $g$; it is enough to assume that $f$ is injective and $|f(w)|\ge|w|^\delta$ for some constant $\delta>0$.
* A (necessarily sparse) language $L$ is **P**-*printable* if there exists a poly-time function $h$ such that $h(1^n)$ outputs the set $\{w\in L:|w|\le n\}$. If there exists a function $f$ as above, then e.g. $\{f(1^n):n\in\mathbb N\}$ is a **P**-printable infinite set of primes. This is a much weaker requirement than the existence of an $f$ as in the Observation, nevertheless even the existence of a **P**-printable infinite set of primes is an open problem; see the discussion in <https://arxiv.org/abs/2109.14764> .
* If you relax the question to allow NP languages on primes that are NP-hard under *randomized* poly-time reductions, then such languages *do* exist, as you can construct $f$ and $g$ as above where $f$ is randomized poly-time (and $g$ is still deterministic).

  E.g., let $f(w)$ be a randomly chosen prime of length $|w'|^2$ whose binary expansion starts with $1w'$, where $w'$ is a prefix-free encoding of $w$ (e.g., if $w=w\_0\dots w\_{n-1}$, let $w'=1w\_01w\_1\dots1w\_{n-1}0$), and let $g(x)$ decode the prefix of $x$.

  This construction can be derandomized assuming [Cramér’s conjecture](https://en.wikipedia.org/wiki/Cram%C3%A9r%27s_conjecture).

> **Comments:**
> **username_0**: Thank you for your insightful and useful answer. I am actually curious as to the consequences of such a problem existing. Perhaps I will post that as another question, pending some further investigations into this matter.  

---

### Answer by username_4 on 2023-07-26. Score: 2

I don't know if it has an official name, but this problem is NP-complete (actually it's a simple "number theory" reformulation of the exact cover by 3-sets problem):

Given a set of $3n$ triprime numbers; find if there is a square-free product of $n$ of them. The problem is NP-complete even if their factors are given in the input.

> **Comments:**
> **username_3**: If you allow as an input a long list of small primes in this manner, then you can trivially encode any problem by “primes”: e.g., encode a string $w_1\dots w_n\in\{0,1\}^n$ by the list $(2+w_1,\dots,2+w_n)$. I don’t think this is what the OP had in mind.  
> **username_4**: @EmilJeřábek: I agree, but the problem in my answer has an almost "natural" interpretation: a list of triprimes as input and asks for a square-free product. Up to my knowledge, I think it's the closest to what the OP asked, but let's see his opinion.  
> **username_0**: @EmilJeřábek, Marzio. The problem might be here that you are measuring complexity relative to n (not even the binary length of n), rather than the binary length of the prime numbers themselves? Perhaps you could clarify this?  
> **username_3**: @EGME Could *you* clarify what you mean by this? The definition of NP and NP-completeness is such that complexity is measured with respect to the total length of the input. Here, the length of the input is not quite the parameter denoted as $n$, but it is close: the input is a list of $9n$ primes, each of binary length $O(\log n)$ (this is not specified in the problem statement, but the reduction showing NP-completeness gives this). Thus, the length of the input, which is the *sum* of the lengths of the primes involved, is $O(n\log n)$, whereas the *individual* primes have length $O(\log n)$.  
> **username_5**: We may assume triprime numbers with no square factors, then each triprime number is equivalent to a set of exactly three primes, and you are looking for n sets with no common element. Map the i-th prime to the number i, and it's the same problem with no primes involved.  
> **username_0**: @EmilJeřábek. Thank, you, you have actually clarified it very nicely. The total input length is exponentially larger than the length of any of the primes. I am looking for a problem where you are working relative to the binary length of the primes themselves.  I guess I did not explain that clearly enough in the post.  
> **username_4**: @EGME: then my answer is useless; if you allow randomization then you can artificially use larger primes (find a set of primes of binary length $O(n)$), but without randomization there are no known methods (see Emil's answer)  

---

