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 Dec 18 '15 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 Dec 18 '15 at 15:43
  • $\begingroup$ @MohammadAl-Turkistany thanks, I will try this. $\endgroup$ – Beginner Dec 18 '15 at 15:47
  • $\begingroup$ @DenisPankratov thanks now I have a concrete example to work with. $\endgroup$ – Beginner Dec 18 '15 at 15:48

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.

| cite | improve this answer | |
  • 2
    $\begingroup$ By the way, ToughSAT is also useful for generating (hard) SAT instances. $\endgroup$ – Juho Dec 19 '15 at 21:46

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.