Combinatorics equips one with methods to find the number of solutions to discrete problems. While this is obviously an important tool for accurate gauges on the average running of an algorithm, I'm interested in whether, and if, how, one can use the knowledge of the number of solutions to improve an algorithm.

More specifically, I'm looking for examples, where having knowledge of the exact count of solutions allows one to improve the running time of the algorithm (significantly, i.e. it should show in $\mathcal O$-notation)

An idea of how such an algorithm might look like, might be this:
For a problem of the kind "Find all possible solutions", we iteratively calculate the next solution using (one/all) previous solutions, but with the catch that every such step has an enormous increase in cost.

For such an algorithm, knowing the number of solutions would allow us to skip the last (and most expensive) step.

What would be an actual algorithm that, when knowing of the number solutions, can be significantly improved?

  • $\begingroup$ I'm not sure if this is what you're asking, but given an algorithm that returns the number of solutions to any $\mathrm{SAT}$ problem in PTIME, it is easy to find some such solution. $\endgroup$ – cody Jul 31 '19 at 1:28
  • $\begingroup$ @cody Hmm, it might, but the picture is still too fuzzy for me. Could you show me an example? $\endgroup$ – Sudix Jul 31 '19 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.