4
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Try to encode instance of integer factoring problem into an instance of integer programming. $\endgroup$ 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$ Dec 18, 2015 at 15:43
  • $\begingroup$ @MohammadAl-Turkistany thanks, I will try this. $\endgroup$
    – Beginner
    Dec 18, 2015 at 15:47
  • $\begingroup$ @DenisPankratov thanks now I have a concrete example to work with. $\endgroup$
    – Beginner
    Dec 18, 2015 at 15:48

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ By the way, ToughSAT is also useful for generating (hard) SAT instances. $\endgroup$
    – Juho
    Dec 19, 2015 at 21:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.