GCSE Link: None
A tractable problem is one that can be solved in polynomial time or better.
Polynomial time is an umbrella term for any time complexity of the form O(nk).
It includes quadratic time (O(n2)), cubic time
(O(n3)), and so on.
The problems solved by Examples 1 to 4 on the previous page are tractable (because constant time, logarithmic time and linear time are all considered "better" than polynomial time). Searching and sorting algorithms (16.06) are also tractable.
An intractable problem is one that cannot be solved in polynomial time or better.
Example 5 on the previous page is intractable, as exponential time is worse than polynomial time. Intractable problems cannot be solved efficiently for larger inputs.
However, there are also problems which cannot be solved using algorithms at all.
A non-computable problem is one with no algorithmic solution.
For example: the halting problem. Given any program as an input, the machine must output whether that program will halt (finish execution) or loop forever.
This was proven to be impossible by Alan Turing in 1936, showing that there are some problems which cannot be solved by a computer.
What is the time complexity of an algorithm to find all permutations of an array? Is this problem tractable or intractable?
The time complexity is O(n!), so it runs in "factorial time" (which is even worse than
exponential time). This is clearly an intractable problem.