3
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 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$
    – Noah Stephens-Davidowitz
    Commented Nov 3, 2017 at 7:20
  • $\begingroup$ @NoahStephens-Davidowitz Isn't that a generalization of 3-partiotion problem? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 3, 2017 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
    Commented Nov 3, 2017 at 12:56
  • $\begingroup$ @Pontus Sub-set product is weakly NP-complete. Your claim is a common mistake. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Nov 3, 2017 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$
    – Marzio De Biasi
    Commented Nov 3, 2017 at 15:50

2 Answers 2

Reset to default
3
$\begingroup$

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

SUBSET SUM OF FACTORIZED SEMIPRIMES "SUBSUMS"

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

Improve this answer
$\endgroup$
3
  • $\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$
    – Mohammad Al-Turkistany
    Commented Nov 4, 2017 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
    Commented Mar 27, 2019 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$
    – Marzio De Biasi
    Commented Mar 27, 2019 at 9:55
1
$\begingroup$

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.

Improve this answer
$\endgroup$

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.