Exam-style question
Try this first
Which statement correctly compares tractable and intractable problems?.
- A.Tractable problems have a polynomial (or less) time solution, whereas intractable problems do not.
- B.Tractable problems require heuristics, whereas intractable problems always have polynomial solutions.
- C.Both types of problem are defined as having no algorithmic solution.
- D.Both types of problem must be solved using heuristic methods.
Model answer
What a good answer should say
- Tractable problems have a polynomial (or less) time solution, whereas intractable problems do not.
Explanation
Why this works
The distinction is based on whether a polynomial (or less) time solution exists. Heuristics are often used for intractable problems, but they do not define both classifications.
Common mistake
No common mistake is linked to this question yet.