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, 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?
-
$\begingroup$ Try to encode instance of integer factoring problem into an instance of integer programming. $\endgroup$Mohammad Al-Turkistany– Mohammad Al-Turkistany2015年12月18日 12:55:51 +00:00Commented Dec 18, 2015 at 12:55
-
3$\begingroup$ 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 (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. $\endgroup$Denis Pankratov– Denis Pankratov2015年12月18日 15:43:18 +00:00Commented Dec 18, 2015 at 15:43
-
$\begingroup$ @DenisPankratov thanks now I have a concrete example to work with. $\endgroup$Beginner– Beginner2015年12月18日 15:48:12 +00:00Commented Dec 18, 2015 at 15:48
1 Answer 1
See Fast Reduction from RSA to SAT 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.
-
2