Skip to topic
    ← Back to course topics

    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

    1. 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
    1. 1Day 1-2: Master the definitions of computable, non-computable, tractable, and intractable, creating flashcards for key terms.
    2. 2Day 3-4: Study Turing's Halting Problem, focusing on the logic of proof by contradiction and why no universal analyser can exist.
    3. 3Day 5-6: Analyse canonical intractable problems such as the Travelling Salesperson Problem and the Knapsack Problem, exploring heuristic alternatives.
    4. 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)
    Explain

    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.

    State / Give

    Provide a brief, precise fact or definition without detailed narrative (e.g. 'State an example of a non-computable problem').

    Discuss

    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)
    Pitfall: Confusing an 'intractable' problem with an 'uncomputable' (or non-computable) problem.
    ❌ Weak Answer (Loses Marks):An intractable problem cannot be solved by a computer because it takes forever.
    Example improved answer:An intractable problem is theoretically computable and an algorithmic solution exists; however, it cannot be solved within a realistic or polynomial time frame for large inputs as its time complexity is exponential (e.g. O(2^n)) or factorial (e.g. O(n!)). In contrast, an uncomputable problem cannot be solved by an algorithm regardless of time or computational resources.
    Examiner Tip: Always specify that intractable problems DO have algorithmic solutions, but their growth rate makes them practically unusable for non-trivial input sizes.
    Pitfall: Failing to explain the Halting Problem in terms of self-contradiction or proof by contradiction.
    ❌ Weak Answer (Loses Marks):The Halting Problem shows that computers crash when they enter infinite loops.
    Example improved answer:The Halting Problem demonstrates that it is impossible to write a general algorithm that can determine, for any given program and input, whether that program will eventually halt or run forever. Alan Turing proved this non-computability using proof by contradiction: if a hypothetically universal halting detector existed, feeding it an inverted self-referential program creates an impossible logical paradox.
    Examiner Tip: Focus on the universal nature of the Halting Problem: no single program can predict the termination of *all* possible programs on *all* inputs.
    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. 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. 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. 3.Step 3: Name a standard intractable problem. State an example such as the Travelling Salesperson Problem (TSP) or Boolean Satisfiability (SAT).
    4. 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.
    Final Answer: Tractable problems are solvable in polynomial time (e.g., O(n^2)), while intractable problems possess exponential or factorial complexity (e.g., O(2^n)) and cannot be solved in practical time frames for large inputs. In practice, problems like the Travelling Salesperson Problem are tackled using heuristics or approximation algorithms that yield satisfactory, near-optimal solutions in reasonable time.

    Question: State what is meant by a non-computable problem and outline Turing's proof of the Halting Problem. [4 marks]

    1. 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. 2.Step 2: Identify the Halting Problem as the primary example of an uncomputable/non-computable problem.
    3. 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. 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.
    Final Answer: A non-computable problem is one for which no algorithm can be written to solve all instances. The Halting Problem asks whether an arbitrary program will halt on a given input. Turing proved it non-computable by contradiction: constructing a program that inverts the verdict of a hypothetical halting detector leads to a logical paradox, proving no general halting algorithm can exist.
    Active Recall Memory Test
    What defines a tractable problem in terms of Big-O complexity?
    Key Fact: A problem that can be solved by an algorithm with polynomial time complexity, O(n^k), where k is a constant.
    What is the key difference between an intractable problem and an uncomputable problem?
    Key Fact: An intractable problem has an algorithm but takes exponential/factorial time; an uncomputable problem has no possible algorithm that works for all cases.
    What theoretical problem proves that some problems cannot be solved by any computer?
    Key Fact: The Halting Problem (formulated and proven by Alan Turing).
    What is a heuristic method and when is it employed?
    Key Fact: A rule of thumb or approximation algorithm used to find an acceptable, near-optimal solution to an intractable problem in reasonable time.
    Frequently Asked Questions
    What is the difference between tractable and intractable problems?
    A tractable problem is one that can be solved in polynomial time (e.g., O(n), O(n log n), O(n^2)), meaning as input sizes grow, execution time remains manageable. An intractable problem is one for which the only known exact algorithms run in super-polynomial time, such as exponential O(2^n) or factorial O(n!). While tractable problems can be practically computed for large datasets, intractable problems quickly overwhelm modern hardware, requiring heuristic approximations.
    Why does more powerful hardware not solve intractable problems?
    Intractable problems grow at exponential or factorial rates. If an algorithm takes O(2^n) operations, increasing the input size n by just 1 doubles the required computing time. Even if you upgrade to a supercomputer that is 1,000 times faster, you only increase the maximum solvable input size n by roughly 10. Hardware gains cannot keep pace with exponential mathematics.
    Can an intractable problem ever become tractable?
    Theoretically, yes, if a revolutionary new algorithm is discovered that solves the problem in polynomial time. Whether every problem whose solution can be verified in polynomial time can also be solved in polynomial time is the famous unsolved 'P versus NP' question. However, for known intractable problems, no such polynomial algorithms currently exist.
    What is the Halting Problem in simple terms?
    The Halting Problem asks whether you can write a master computer program that can inspect any other program and its input, and correctly determine whether it will finish running or get stuck in an infinite loop. Alan Turing proved mathematically that it is impossible to write such an algorithm that works accurately for all conceivable programs. It stands as the premier example of an uncomputable decision problem.
    What is a heuristic and why do we use it in Computer Science?
    A heuristic is an algorithm designed to solve a problem faster than classic methods by trading optimality, completeness, or precision for speed. Instead of finding the guaranteed absolute best solution—which could take centuries for intractable problems—a heuristic provides a 'good enough' or near-optimal solution in polynomial time. Common examples include greedy search, genetic algorithms, and the A* pathfinding algorithm.