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

$\endgroup$
  • 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 Nov 3 '17 at 7:20
  • $\begingroup$ @NoahStephens-Davidowitz Isn't that a generalization of 3-partiotion problem? $\endgroup$ – Mohammad Al-Turkistany 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$ – Mohammad Al-Turkistany 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$ – Marzio De Biasi Nov 3 '17 at 15:50
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$.

$\endgroup$
  • $\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 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 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 Mar 27 at 9:55
0
$\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.

$\endgroup$

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.