Some problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's GI result). However, the fixed-point free GA problem is NP-complete.

Also, Factoring decision problem has sub-exponential time algorithm and it is not believed to be NP-complete. Meanwhile, a variant of factoring problem is NP-complete.

Subset-sum and partition problems are weakly NP-complete problems since they have pseudo-polynomial time algorithms. I am interested in their variants that are strongly NP-complete.

Are there known variants of subset-sum or partition problem that are strongly NP-complete?

P.S. I am not interested in 3-partition problem.

  • 1
    $\begingroup$ One way to do this is to "trade bit length for dimensions." I.e., given $m$ n-dimensional vectors $a_1,\ldots,a_m$, does there exist a subset that sums to some other vector $s$? You can effectively simulate binary addition on $n$ bits by such vectors, with a small amount of overhead, so there's an easy reduction from SubsetSum to this problem that only uses small numbers. Maybe this is cheating, though? $\endgroup$ Nov 3 '17 at 7:20
  • $\begingroup$ @NoahStephens-Davidowitz Isn't that a generalization of 3-partiotion problem? $\endgroup$ Nov 3 '17 at 12:11
  • $\begingroup$ Changing the arithmetic operator can (obviously) change the difficulty of the problem. For example, subset-product is strongly NP-complete, at least if we take some care in how to represent the target product. $\endgroup$
    – Pontus
    Nov 3 '17 at 12:56
  • $\begingroup$ @Pontus Sub-set product is weakly NP-complete. Your claim is a common mistake. $\endgroup$ Nov 3 '17 at 13:26
  • 2
    $\begingroup$ @MohammadAl-Turkistany: The common version is weakly NPC, but as Pontus said it can be easily converted to strongly NPC "... if we take some care in how to represent the target product ...". For example the following is strongly NPC: given a set of integers $A$ and $k$ find a subset of integers whose product is equal to the $k$-th primorial. I have described another strongly NPC variant on my blog: Square free subset product $\endgroup$ Nov 3 '17 at 15:50

It's like cheating, but if you change the representation of the numbers in the input then the problem becomes strongly NPC:


Input: A list of $N+1$ integers: $q_0$ and $A = \{q_1, ..., q_N\}$ each one represented as a (sub)sum of factorized (semiprime) integers; i.e. $q_i$ is given as $p_{i,1} 2^{a_{i,1}} + ... + p_{i,m_i} 2^{a_{i,m_i}}$ where $p_{i,j} \geq 3$ is a prime and $a_{i,j}$ is its "shift" exponent (in other words the input is the list of integers $p_{1,1}, a_{1,1}, p_{1,2}, a_{1,2}, ..., p_{2,1}, a_{2,1}, p_{2,2}, a_{2,2}, ...$)

Output: Does there exist a subset of $A' \subseteq A$ such that $\sum_{q \in A'} q = q_0 $?

Easy reduction from the strongly NPC problem $X3C$.

  • $\begingroup$ Thank you Marzio for your answer. I am not interested in variants that utilize number representations. I am aware of your answer since a read here: cstheory.stackexchange.com/questions/16253/… $\endgroup$ Nov 4 '17 at 9:29
  • $\begingroup$ Could you give a few details on the reduction from X3C? I do not see how the prime factorisations survive the sum. $\endgroup$
    – Philipp
    Mar 27 '19 at 1:50
  • 1
    $\begingroup$ @Philipp: you're right, "factorized integers" is not exactly what I had in mind; I changed the answer; clearly "subsums of semiprimes" it's a less natural number representation. $\endgroup$ Mar 27 '19 at 9:55

I found a strongly NP-complete variant of partition (which does not take advantage of special number representations ). It is known as Product Partition problem (similar to partition problem but with addition operation replaced by multiplication operation). The proof was given by Ng et al.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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