<p>See <a href="https://cstheory.stackexchange.com/q/6755/5038">Fast Reduction from RSA to SAT</a> for some ways to get hard instances of SAT.  Then, you can use the known reductions to turn these into hard instances for ILP.  You could also use the SAT instances at <a href="http://www.satcompetition.org/" rel="nofollow noreferrer">http://www.satcompetition.org/</a>, too.</p>

CC BY-SA 3.0
2015-12-19T21:46:28.930Z
By the way, [ToughSAT](https://toughsat.appspot.com/) is also useful for generating (hard) SAT instances.
Juho
CC BY-SA 3.0
2015-12-18T22:58:08.297Z
2015-12-18T22:58:08.297Z
2017-04-13T12:32:28.743Z
D.W.
<p>I am trying to find a way to find a worst-case input for a black-box implementation of an algorithm with worst-case exponential runtime.</p>

<p>The problem that the program solves (integer linear programming) is <a href="https://en.wikipedia.org/wiki/Integer_programming" rel="nofollow">NP-hard</a>, but since the proof is by reduction from vertex cover, there is no construction of a hard subset or such. Also vertex cover is in NP due to a reduction from 3SAT. Now for 3SAT it is in no way certain that a hard case for a given 3sat solver would translate to a hard problem for one of my black-box ILP implementations.</p>

<p>Is there a systematic way to find a worst-case runtime example for a given problem of size n?</p>

CC BY-SA 3.0
2015-12-18T12:55:51.647Z
Try to encode instance of integer factoring problem into an instance of integer programming.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-12-18T15:43:18.293Z
Are you looking for concrete instances? If so then in addition to the above answer regarding encoding integer factoring, I would recommend to base such instances on the unsolved RSA challenges (https://en.m.wikipedia.org/wiki/RSA_Factoring_Challenge). Back in the days RSA challenge organizers would have paid large amounts of money for factoring these numbers.
Denis Pankratov
CC BY-SA 3.0
2015-12-18T15:47:45.670Z
@MohammadAl-Turkistany thanks, I will try this.
Beginner
CC BY-SA 3.0
2015-12-18T15:48:12.970Z
@DenisPankratov thanks now I have a concrete example to work with.
Beginner
<np-hardness>
Find worst case input for a program solving an NP-hard problem
Beginner
# Find worst case input for a program solving an NP-hard problem

(Asked by: username_0 on 2015-12-18)

I am trying to find a way to find a worst-case input for a black-box implementation of an algorithm with worst-case exponential runtime.

The problem that the program solves (integer linear programming) is [NP-hard](https://en.wikipedia.org/wiki/Integer_programming), but since the proof is by reduction from vertex cover, there is no construction of a hard subset or such. Also vertex cover is in NP due to a reduction from 3SAT. Now for 3SAT it is in no way certain that a hard case for a given 3sat solver would translate to a hard problem for one of my black-box ILP implementations.

Is there a systematic way to find a worst-case runtime example for a given problem of size n?

**Tags:** np-hardness
> **Comments:**
> **username_1**: Try to encode instance of integer factoring problem into an instance of integer programming.  
> **username_2**: Are you looking for concrete instances? If so then in addition to the above answer regarding encoding integer factoring, I would recommend to base such instances on the unsolved RSA challenges (https://en.m.wikipedia.org/wiki/RSA_Factoring_Challenge). Back in the days RSA challenge organizers would have paid large amounts of money for factoring these numbers.  
> **username_0**: @MohammadAl-Turkistany thanks, I will try this.  
> **username_0**: @DenisPankratov thanks now I have a concrete example to work with.  

---

## 1 answers

### Answer by username_3 on 2015-12-18. Score: 1 | Accepted answer

See [Fast Reduction from RSA to SAT](https://cstheory.stackexchange.com/q/6755/5038) for some ways to get hard instances of SAT. Then, you can use the known reductions to turn these into hard instances for ILP. You could also use the SAT instances at <http://www.satcompetition.org/>, too.

> **Comments:**
> **username_4**: By the way, [ToughSAT](https://toughsat.appspot.com/) is also useful for generating (hard) SAT instances.  

---

