6
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Jul 25, 2023 at 18:30
  • 1
    $\begingroup$ For whatever reason this comes to my mind arxiv.org/abs/2109.14764 $\endgroup$
    – Tayfun Pay
    Jul 26, 2023 at 4:58
  • $\begingroup$ @TayfunPay Thanks for the link! I mentioned it in my answer. $\endgroup$ Jul 26, 2023 at 9:07
  • $\begingroup$ @TayfunPay. Thanks for pointing out that interesting article. $\endgroup$
    – EGME
    Jul 26, 2023 at 10:57

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – EGME
    Jul 25, 2023 at 20:26
2
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 26, 2023 at 7:45
  • $\begingroup$ @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. $\endgroup$ Jul 26, 2023 at 9:03
  • $\begingroup$ @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? $\endgroup$
    – EGME
    Jul 26, 2023 at 14:47
  • $\begingroup$ @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)$. $\endgroup$ Jul 26, 2023 at 15:01
  • 1
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Jul 26, 2023 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.