1
$\begingroup$

Say I want to solve a set of problems. I know that I can map my problem as a problem that is known to be hard in the general case (say, inference in Bayesian networks). But my set only contains instances which will map to easy instances - (say, having a tree-structure when cast to a BN inference problem)

I know BNs with tree-structures have linear-time inference algorithms. If I didn't, I may have given up on exact solutions in favour of loose approximations.

(2nd, looser example: I find myself needing to solve SAT, but turns out I can easily reduce all my problem instances to 2-SAT)

Is there a common approach to determine whether a given subset of a hard problem is hard or not? How does one typically approach this? Are these well studied

Improve this question
$\endgroup$
1
  • $\begingroup$ Does "look it up in Garey/Johnson, which often lists more tractable special cases" count as "an approach"? ;-) $\endgroup$
    – Ulrich Schwarz
    Jun 15 at 6:33

1 Answer 1

Reset to default
3
$\begingroup$

This is a very broad topic. Every problem is a special case of some hard problem. For instance, most problems (both hard and easy ones) can be viewed as a special case of the halting problem, but that doesn't really help us distinguish hard from easy problems. It all depends on the details. I don't think there's any general answer at this level of abstraction.

Improve this answer
$\endgroup$

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.