1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 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
    Commented Sep 3, 2016 at 20:15
  • $\begingroup$ Yes, now it's a list question. Above comment applies. $\endgroup$
    – Raphael
    Commented Sep 4, 2016 at 7:34

0

Reset to default

Your Answer

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