Loading...
Some tasks are expensive to solve, while others cannot be solved by a general algorithm at all. These are different limitations and require different explanations.
What you'll be able to do
A computable task has an algorithmic solution, but its resource requirements may exceed available time or memory. Exponential or factorial search can become impractical quickly as the input grows. A faster processor may help small cases without making arbitrary large cases feasible.
The specification calls problems with a polynomial-or-better time solution tractable and those without such a solution intractable. This is an asymptotic classification, not a guarantee that every polynomial algorithm is fast enough in practice. Large exponents and constants still matter.
A heuristic seeks a useful solution or good practical performance without necessarily guaranteeing the optimum or the required bound for every case. It can be appropriate when exhaustive optimisation is impractical. State what guarantee is being relaxed and how solution quality will be evaluated.
A problem for which no polynomial algorithm is currently known is not thereby proved to have none. Avoid treating an open complexity question as settled. AQA does not require students to resolve such questions; it requires a clear distinction between the defined categories and practical limits.
The Halting problem asks for one general algorithm that, given any program and its input, always correctly decides whether that execution eventually stops. No such universally correct terminating decider exists. This is not merely a shortage of processor speed or a program that has not yet been written.
Particular cases can still be decided: a simple bounded loop terminates, while an unconditional loop with no exit does not. A timeout can show that a run has not stopped yet, but cannot generally prove that it never will. The result limits universal automated analysis without preventing useful checks of restricted program classes.
Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.
Common mistakes to avoid
Key takeaways
Test yourself
Answer a few questions, then review anything you missed.
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.