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

<p>SUBSET SUM OF FACTORIZED SEMIPRIMES "SUBSUMS"</p>

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

<p><strong>Output</strong>: Does there exist a subset of <span class="math-container">$A' \subseteq A$</span>  such that <span class="math-container">$\sum_{q \in A'} q = q_0 $</span>?</p>

<p>Easy reduction from the strongly NPC problem <span class="math-container">$X3C$</span>.</p>

CC BY-SA 4.0
2019-03-27T01:50:37.060Z
Could you give a few details on the reduction from X3C? I do not see how the prime factorisations survive the sum.
Philipp
CC BY-SA 4.0
2019-03-27T09:55:26.793Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2017-11-04T09:29:41.583Z
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: https://cstheory.stackexchange.com/questions/16253/list-of-strongly-np-hard-problems-with-numerical-data
Mohammad Al-Turkistany
CC BY-SA 4.0
2017-11-03T16:12:37.837Z
2019-03-27T09:53:49.157Z
2019-03-27T09:53:49.157Z
Marzio De Biasi
<p>I found a <em>strongly</em> 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 <a href="http://www.sciencedirect.com/science/article/pii/S0377221710003905" rel="nofollow noreferrer">proof was given by Ng et al</a>.</p>

CC BY-SA 3.0
2017-11-20T15:19:10.303Z
2017-11-20T20:10:42.140Z
2017-11-20T20:10:42.140Z
Mohammad Al-Turkistany
<p>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. </p>

<p>Also, Factoring decision problem has sub-exponential time algorithm and it is not believed to be NP-complete. Meanwhile, a <a href="https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring">variant of factoring problem</a> is NP-complete.</p>

<p>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.</p>

<blockquote>
  <p>Are there known variants of subset-sum or partition problem that are <em>strongly</em> NP-complete? </p>
</blockquote>

<p>P.S. I am not interested in 3-partition problem.</p>

CC BY-SA 3.0
2017-11-03T07:20:36.460Z
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?
Noah Stephens-Davidowitz
CC BY-SA 3.0
2017-11-03T12:11:43.200Z
@NoahStephens-Davidowitz Isn't that a generalization of 3-partiotion problem?
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-03T12:56:41.987Z
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.
Pontus
CC BY-SA 3.0
2017-11-03T13:26:05.687Z
@Pontus Sub-set product is weakly NP-complete. Your claim is a common mistake.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-11-03T15:50:07.250Z
@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](http://www.nearly42.org/npc-pills/npc-pill-004/)
Marzio De Biasi
CC BY-SA 3.0
2017-11-03T19:17:32.310Z
@MarzioDeBiasi: This was exactly what I had in mind. Representing $k$ by its prime factorization should also work.
Pontus
<cc.complexity-theory><partition-problem><subset-sum>
Strongly NP-complete variants of subset sum or partition problem
Mohammad Al-Turkistany
# Strongly NP-complete variants of subset sum or partition problem

(Asked by: username_0 on 2017-11-02)

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](https://cstheory.stackexchange.com/questions/4769/an-np-complete-variant-of-factoring) 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.

**Tags:** cc.complexity-theory, partition-problem, subset-sum
> **Comments:**
> **username_1**: 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?  
> **username_0**: @NoahStephens-Davidowitz Isn't that a generalization of 3-partiotion problem?  
> **username_2**: 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.  
> **username_0**: @Pontus Sub-set product is weakly NP-complete. Your claim is a common mistake.  
> **username_3**: @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](http://www.nearly42.org/npc-pills/npc-pill-004/)  
> **username_2**: @MarzioDeBiasi: This was exactly what I had in mind. Representing $k$ by its prime factorization should also work.  

---

## 2 answers

### Answer by username_3 on 2017-11-03. Score: 3

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

> **Comments:**
> **username_0**: 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: https://cstheory.stackexchange.com/questions/16253/list-of-strongly-np-hard-problems-with-numerical-data  
> **username_4**: Could you give a few details on the reduction from X3C? I do not see how the prime factorisations survive the sum.  
> **username_3**: @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.  

---

### Answer by username_0 on 2017-11-20. Score: 1

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](http://www.sciencedirect.com/science/article/pii/S0377221710003905).


---

