<p>Here is a <a href="http://www.stats.ox.ac.uk/people/academic_staff/colin_mcdiarmid/?a=4138" rel="nofollow">strongly $NP$-complete</a> problem (with numerical data as you requested):</p>

<p><strong>Schur Triples problem</strong>:</p>

<p>Input: list of 3N <strong>distinct</strong> positive integers</p>

<p>Question: Is there a partition of the list into N triples $(a_i, b_i, c_i)$ such that $a_i + b_i= c_i$ for each triple $i$?</p>

<p>The condition that all numbers must be <strong>distinct</strong> makes the problem very interesting and McDiarmid calls it a <em>surprisingly troublesome</em> . </p>

CC BY-SA 3.0
2015-01-21T17:29:24.937Z
2015-01-22T09:30:55.640Z
2015-01-22T09:30:55.640Z
Mohammad Al-Turkistany
<p>Here's another strongly $NP$-hard problem:  From the domain of theoretic scheduling and combinatorial optimization, the makespan problem on identical parallel machines (denoted commonly as $P||C_{max}$ in the literature).  Note that some of the hardest scheduling problems almost all have this as a special case (e.g., the makespan problem on unrelated parallel machines.  </p>

<p>It's strongly $NP$-hard, because you can reduce from the $3$-partition problem (,see <a href="http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec10.pdf" rel="nofollow">http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec10.pdf</a> section 10.5).</p>

<p>Hope this helps!</p>

CC BY-SA 3.0
2015-01-27T02:55:59.190Z
2015-01-27T02:55:59.190Z
PageWizard
<p>While thinking about possible answers I came up with this simple numeric strongly NP-complete problem:</p>

<p>SQUARE FREE SUBSET PRODUCT: Given $3N$ integers, find $N$ of them whose product is square free.</p>

<p>Proof sketch: starting from a an Exact Cover by 3 sets (X3C) instance (strongly NPC) label each element of the universe with a distinct prime (you can generate $3|X|$ of them in polynomial time); then convert every triple $(x,y,z)$ of the subsets to $xyz$.</p>

<p>I didn't find it anywhere, so it can be somewhat "original".</p>

<p>It obviously resembles the better known SUBSET PRODUCT (which is not strongly NPC due to the presence of the target product $B$, see David S. Johnson: The NP-Completeness Column: An Ongoing Guide. 393-405).</p>

<p>It can also be hacked a little bit to get other variants, like:</p>

<ul>
<li>Given $3N$ integers, find $N$ of them whose product is a perfect $21$-th power;</li>
<li>Given $N$ integers, find a subset whose product is the 3N-th primorial. (kind of cheating :-)</li>
</ul>

CC BY-SA 3.0
2015-01-23T23:00:39.240Z
@domotorp: I deleted the question;I copy/paste here your comment about transforming the constraint into "...find a subset whose product is a square free number greater than M...":"First consider that you multiply each number by a different,very large prime, such that all these are about the same size. Then selecting N numbers would become equivalent to obtaining a large product. We cannot (yet) generate large primes in P, but in fact we don't need them - instead of each prime we can use relative prime square-free numbers,and those we can generate by computing the first polynomially many primes
Marzio De Biasi
CC BY-SA 3.0
2015-01-23T22:38:30.237Z
2015-01-23T22:51:13.717Z
2015-01-23T22:51:13.717Z
Marzio De Biasi
<p>Cieliebak in his <a href="http://www.ti.inf.ethz.ch/pw/publications/diss/CieliebakThesis.pdf" rel="nofollow">Ph.D. Dissertation</a> proved several problems to be strongly NP-complete. Specifically, the Double Digest problem and k-Equal Sum Subsets problem (when $k= \Omega(n)$ ) are strongly $NP$-complete.</p>

CC BY-SA 3.0
2015-01-24T09:43:17.033Z
2015-01-24T09:51:53.067Z
2015-01-24T09:51:53.067Z
Mohammad Al-Turkistany
<p>I am looking for <a href="http://en.wikipedia.org/wiki/Strongly_NP-complete" rel="noreferrer">strongly NP-hard problems</a> for a reduction.
So far I have found the following problems:</p>

<ul>
<li>3-partition problem</li>
<li>bin-packing problem</li>
<li>Numerical 3-dimensional matching</li>
<li>TSP</li>
<li>Any NP-complete problem without numerical data, e.g., SATISFIABILITY, HAMILTONIAN
CYCLE, 3-COLOURABILITY.</li>
</ul>

<p>Does anyone know of a list of strongly NP-hard problems?</p>

<p>If not, let's build one here.
Do you know of other problems with numerical data that are strongly NP-hard?</p>

<p>I'm particularly interested in strongly NP-hard problems on weighted graphs.</p>

CC BY-SA 3.0
2013-01-28T13:03:38.217Z
Make your question self-contained by defining "strongly".
Tyson Williams
CC BY-SA 3.0
2013-01-28T13:30:07.997Z
Longest path is a generalization of Hamiltonian Path, so it's strongly NP-hard.
Michael Lampis
CC BY-SA 3.0
2013-01-29T03:40:18.870Z
(1) Is “strongly NP” a typo for “strongly NP-hard”?  (2) I do not think that “we can make one here.”
Tsuyoshi Ito
CC BY-SA 3.0
2015-01-24T19:51:09.463Z
rainbow coloring seems to be hard wrt treewidth, maybe strongly NP hard also...?
vzn
<np-hardness><big-list><hamiltonian-paths>
List of strongly NP-hard problems with numerical data
sigal maon
# List of strongly NP-hard problems with numerical data

(Asked by: username_0 on 2013-01-28)

I am looking for [strongly NP-hard problems](http://en.wikipedia.org/wiki/Strongly_NP-complete) for a reduction.
So far I have found the following problems:

* 3-partition problem
* bin-packing problem
* Numerical 3-dimensional matching
* TSP
* Any NP-complete problem without numerical data, e.g., SATISFIABILITY, HAMILTONIAN
  CYCLE, 3-COLOURABILITY.

Does anyone know of a list of strongly NP-hard problems?

If not, let's build one here.
Do you know of other problems with numerical data that are strongly NP-hard?

I'm particularly interested in strongly NP-hard problems on weighted graphs.

**Tags:** np-hardness, big-list, hamiltonian-paths

> **Comments:**
> **username_1**: Make your question self-contained by defining "strongly".  
> **username_2**: Longest path is a generalization of Hamiltonian Path, so it's strongly NP-hard.  
> **username_3**: (1) Is “strongly NP” a typo for “strongly NP-hard”?  (2) I do not think that “we can make one here.”  
> **username_4**: rainbow coloring seems to be hard wrt treewidth, maybe strongly NP hard also...?  

---

## 4 answers

### Answer by username_5 on 2015-01-21. Score: 4

Here is a [strongly $NP$-complete](http://www.stats.ox.ac.uk/people/academic_staff/colin_mcdiarmid/?a=4138) problem (with numerical data as you requested):

**Schur Triples problem**:

Input: list of 3N **distinct** positive integers

Question: Is there a partition of the list into N triples $(a\_i, b\_i, c\_i)$ such that $a\_i + b\_i= c\_i$ for each triple $i$?

The condition that all numbers must be **distinct** makes the problem very interesting and McDiarmid calls it a *surprisingly troublesome* .


---

### Answer by username_6 on 2015-01-27. Score: 0

Here's another strongly $NP$-hard problem: From the domain of theoretic scheduling and combinatorial optimization, the makespan problem on identical parallel machines (denoted commonly as $P||C\_{max}$ in the literature). Note that some of the hardest scheduling problems almost all have this as a special case (e.g., the makespan problem on unrelated parallel machines.

It's strongly $NP$-hard, because you can reduce from the $3$-partition problem (,see <http://www.cs.cmu.edu/afs/cs/academic/class/15854-f05/www/scribe/lec10.pdf> section 10.5).

Hope this helps!


---

### Answer by username_7 on 2015-01-23. Score: 0

While thinking about possible answers I came up with this simple numeric strongly NP-complete problem:

SQUARE FREE SUBSET PRODUCT: Given $3N$ integers, find $N$ of them whose product is square free.

Proof sketch: starting from a an Exact Cover by 3 sets (X3C) instance (strongly NPC) label each element of the universe with a distinct prime (you can generate $3|X|$ of them in polynomial time); then convert every triple $(x,y,z)$ of the subsets to $xyz$.

I didn't find it anywhere, so it can be somewhat "original".

It obviously resembles the better known SUBSET PRODUCT (which is not strongly NPC due to the presence of the target product $B$, see David S. Johnson: The NP-Completeness Column: An Ongoing Guide. 393-405).

It can also be hacked a little bit to get other variants, like:

* Given $3N$ integers, find $N$ of them whose product is a perfect $21$-th power;
* Given $N$ integers, find a subset whose product is the 3N-th primorial. (kind of cheating :-)

> **Comments:**
> **username_7**: @domotorp: I deleted the question;I copy/paste here your comment about transforming the constraint into "...find a subset whose product is a square free number greater than M...":"First consider that you multiply each number by a different,very large prime, such that all these are about the same size. Then selecting N numbers would become equivalent to obtaining a large product. We cannot (yet) generate large primes in P, but in fact we don't need them - instead of each prime we can use relative prime square-free numbers,and those we can generate by computing the first polynomially many primes  

---

### Answer by username_5 on 2015-01-24. Score: 0

Cieliebak in his [Ph.D. Dissertation](http://www.ti.inf.ethz.ch/pw/publications/diss/CieliebakThesis.pdf) proved several problems to be strongly NP-complete. Specifically, the Double Digest problem and k-Equal Sum Subsets problem (when $k= \Omega(n)$ ) are strongly $NP$-complete.


---

