4.4.4.5 Classification of algorithmic problems Flashcards
1
Q
What is meant by a tractable problem?
A
Problems can be solved by computer algorithms that run in polynomial time
2
Q
What might a programmer do if they have to solve an intractable problem?
A
Use of heuristic; algorithm that makes a guess based on experience, provides a close-to-optimal solution that only works in some cases
Relax some of the constraints on the solution - solve simpler version of problem
