When, beyond theoretical exercises, do we care how many solutions we can find for something?

I had an analogous question for TMs before - why is it useful to study machines that can only deliver acceptance and rejection as output? Here, the answer (at least in a practical context) seems more clear - find a solution (e.g., a shortest path in a shortest path problem) is a matter of poly-time reduction to yes/no answers. For #P problems, reduction is equally obvious, but not useful, since you're solving a problem at least as hard.

  • 2
    $\begingroup$ We don't have a strict policy for list questions, but there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$
    – Raphael
    Sep 3 '16 at 20:15
  • $\begingroup$ Yes, now it's a list question. Above comment applies. $\endgroup$
    – Raphael
    Sep 4 '16 at 7:34

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.