# NP-complete problems where the inputs are prime numbers

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?

• You might find something here - en.wikipedia.org/wiki/List_of_NP-complete_problems. if there is such a problem i doubt if its well-known. Jul 25, 2023 at 18:30
• For whatever reason this comes to my mind arxiv.org/abs/2109.14764 Jul 26, 2023 at 4:58
• @TayfunPay Thanks for the link! I mentioned it in my answer. Jul 26, 2023 at 9:07
• @TayfunPay. Thanks for pointing out that interesting article.
– EGME
Jul 26, 2023 at 10:57

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, 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.

• 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
Jul 25, 2023 at 20:26

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.

• 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. Jul 26, 2023 at 7:45
• @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. Jul 26, 2023 at 9:03
• @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
Jul 26, 2023 at 14:47
• @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)$. Jul 26, 2023 at 15:01
• 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. Jul 26, 2023 at 15:23