Classification of algorithmic problems — AQA A-Level Computer Science
Classification of algorithmic problems categorises computational tasks based on solvability and resource complexity, distinguishing computable problems from non-computable ones like the Halting Problem, and tractable polynomial-time problems from intractable exponential ones. Understanding whether a problem falls into P, NP, or non-computable classes is essential for assessing theoretical limits and selecting appropriate algorithmic strategies like heuristics in AQA A-Level Computer Science.
Classification of algorithmic problems explained
This statement asks you to know the two broad categories into which algorithms, or the problems they solve, are classified.
Read the full explanation
The classification is made according to how the time needed to solve a problem grows as the size of its input grows. One category is tractable problems, which can be solved in polynomial time or faster, meaning the running time grows at a manageable rate such as n, n² or n³. The other category is intractable problems, for which no solution is known that runs in polynomial time, so the running time grows very rapidly as the input grows. For example, sorting a list of 1000 items with an efficient algorithm is tractable, whereas checking every possible route through a large network to find the optimal one may require exponential time and so is intractable. You should be able to name both categories and state the difference between them in terms of time complexity.
Your focus
- Know that algorithms may be classified as being either:
Which command word is this?
Set out the causes, reasons, or mechanics of a concept clearly. For example, explain why a problem is intractable by discussing input sizes and exponential time complexity curves.
Classification of algorithmic problems exam tips
Topic Overview
Classification of algorithmic problems categorises tasks according to their theoretical computability and computational efficiency. In AQA A-Level Computer Science, this involves categorising problems into computable versus non-computable, and dividing computable problems into tractable (polynomial time) and intractable (exponential/factorial time) classes.
This topic forms the theoretical foundation of computational complexity. It provides students with the critical framework needed to evaluate limits of computation, determine when an optimal algorithm is achievable, and recognise when to adopt heuristic approximations for challenging computational tasks.
Key Concepts
- →Computable vs Non-Computable: Computable problems have an effective algorithm capable of solving all valid instances; non-computable problems (e.g., the Halting Problem) cannot be solved by any algorithm regardless of time or resources.
- →Tractable Problems: Problems solvable in polynomial time, denoted as O(n^k) where k is a constant (e.g., sorting, searching, graph traversal), making them feasible for practical computation.
- →Intractable Problems: Solvable problems whose execution time grows exponentially (e.g., O(2^n)) or factorially (e.g., O(n!)), rendering them practically unsolvable for anything beyond small inputs.
- →Heuristic Approximations: Practical algorithmic strategies used to find good-enough or near-optimal solutions to intractable problems within acceptable time limits, trading optimality for efficiency.
Marking Points
- Names tractable and intractable as the two classifications of algorithms or problems
- States that tractable problems have solutions that run in polynomial time or better
- States that intractable problems have no known polynomial-time solution
- Links the classification to how running time grows with input size
Examiner Tips
- 💡Learn the two terms exactly as tractable and intractable, and use them in your answer
- 💡Remember the test is whether a polynomial-time solution exists
- 💡Check whether an option refers to input size or running time before choosing it
- 💡Always use formal time complexity notations when discussing tractability; contrast polynomial O(n^k) with exponential O(2^n) or factorial O(n!).
- 💡When asked how to solve intractable problems in real-world scenarios, always use the keyword 'heuristic' and clearly explain that it gives an approximate or near-optimal answer, not a guaranteed optimal one.
- 💡Clearly separate theoretical computability from practical efficiency in essay questions to access the top mark band.
Common Mistakes
- Confuses intractable with impossible; intractable problems can still be solved, but only slowly for large inputs
- Classifies algorithms by programming language or hardware instead of by time complexity
- Describes the two categories without naming them
- Believing that an intractable problem cannot be solved at all. Correction: Intractable problems *can* be solved algorithmically, but their time complexity requires an impractical amount of time for large inputs.
- Assuming that faster computer hardware will eventually make intractable problems tractable. Correction: Because exponential growth drastically outpaces polynomial hardware gains, doubling processor speed only adds a tiny constant increase to solvable input size n.
- Thinking the Halting Problem simply means a program containing a 'while True' loop. Correction: The Halting Problem addresses the impossibility of a *general universal analyser* predicting termination for *any* arbitrary program and input.
Revision Plan
- 1Day 1-2: Master the definitions of computable, non-computable, tractable, and intractable, creating flashcards for key terms.
- 2Day 3-4: Study Turing's Halting Problem, focusing on the logic of proof by contradiction and why no universal analyser can exist.
- 3Day 5-6: Analyse canonical intractable problems such as the Travelling Salesperson Problem and the Knapsack Problem, exploring heuristic alternatives.
- 4Day 7: Practise AQA past paper exam questions, specifically targeting 4-mark and 6-mark comparative and evaluative questions.
Exam Question Types
- 📋Definition and Distinction Questions: 2-3 mark questions asking to define tractable/intractable or computable/non-computable with exact terminology.
- 📋Halting Problem Explanations: 3-4 mark questions requiring an explanation of what the problem is and why it cannot be solved algorithmically.
- 📋Scenario/Heuristic Evaluation: 6-mark questions describing a computationally heavy problem (like route planning) and asking students to evaluate tractability and propose heuristic methods.
Command Word Expectations (AQA)
Set out the causes, reasons, or mechanics of a concept clearly. For example, explain why a problem is intractable by discussing input sizes and exponential time complexity curves.
Provide a brief, precise fact or definition without detailed narrative (e.g. 'State an example of a non-computable problem').
Explore multiple perspectives or dimensions of a topic, such as contrasting exact algorithmic solutions with heuristic methods for intractable problems, evaluating their trade-offs.
How Students Lose Marks (Examiner Pitfalls)
Step-by-Step Worked Solutions
Question: Explain the difference between tractable and intractable problems. Describe how a computer scientist would address an intractable problem in practice, referencing an example problem. [6 marks]
- 1.Step 1: Define tractable problems with reference to Big-O notation. A tractable problem is one that can be solved in polynomial time (e.g. O(n^k) such as O(n) or O(n^2)), meaning it is feasible to solve for reasonable input sizes.
- 2.Step 2: Define intractable problems. An intractable problem has a known algorithmic solution, but its time complexity is super-polynomial, exponential (e.g. O(2^n)), or factorial (e.g. O(n!)), making computation impossible within practical time limits for large values of n.
- 3.Step 3: Name a standard intractable problem. State an example such as the Travelling Salesperson Problem (TSP) or Boolean Satisfiability (SAT).
- 4.Step 4: Explain practical resolution techniques. Since finding an exact optimal solution is computationally infeasible, computer scientists use heuristic approaches or approximation algorithms (e.g., genetic algorithms, A* search, or greedy nearest-neighbour) that provide an acceptable, near-optimal solution in polynomial time.
Question: State what is meant by a non-computable problem and outline Turing's proof of the Halting Problem. [4 marks]
- 1.Step 1: Define a non-computable problem. State that it is a decision problem for which no algorithm can ever be constructed that leads to a correct yes-or-no answer in every case.
- 2.Step 2: Identify the Halting Problem as the primary example of an uncomputable/non-computable problem.
- 3.Step 3: Explain the structure of the proof. Turing assumed an algorithm H exists that decides if program P halts on input I.
- 4.Step 4: Detail the contradiction. Construct a new program, say D, that takes another program as input. D calls H with itself; if H says D halts, D loops forever, and if H says D loops, D halts immediately. This produces an impossible contradiction, proving H cannot exist.