Exam-style question
Try this first
Define the terms tractable and intractable in the context of algorithmic problems. Then explain why the distinction is useful when considering how to tackle a problem.
Model answer
What a good answer should say
- A tractable problem is one that has a polynomial (or less) time solution.
- An intractable problem is one that has no polynomial (or less) time solution.
- The distinction helps identify whether a problem has a solution whose time is polynomial (or less); when a problem is intractable, heuristic methods are often considered as a way of tackling it.
Explanation
Why this works
A complete answer must include both definitions and link the classification to the use of heuristic methods for intractable problems. It should not claim that an intractable problem has no solution at all; the specification says that it has no polynomial (or less) time solution.
Common mistake
No common mistake is linked to this question yet.