Lesson 4.4.4.4

4.4.4.4 Limits of computation and computable problems Quiz: AQA Computer Science, Unit 4

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson 4.4.4.4, Limits of computation and computable problems: 20 multiple choice questions for the AQA Computer Science (7517), Unit 4: Theory of computation, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. What limits what can be computed in practice?

    • The length of the program's name
    • The number of programmers involved
    • Algorithmic complexity and hardware
    • The number of programmers involved in writing the software for the system

  2. A tractable problem is one that has what kind of solution time?

    • Constant regardless of size
    • Exponential in the size of the problem, growing quickly as the input becomes large
    • Unknown and unbounded
    • Polynomial, or less, in the size of the problem

  3. An intractable problem is one that:

    • Has no polynomial, or less, time solution
    • Is always solved by sorting
    • Can never be written down
    • Has a constant time solution

  4. Heuristic methods are often used when tackling what kind of problem?

    • Constant-time problems
    • Problems stored in a database
    • Problems with no inputs
    • Intractable problems

  5. Which of these is an example of a tractable problem?

    • Sorting a list of numbers
    • Trying every combination of an unbounded set
    • Checking every possible subset of n items for large n
    • Finding every possible ordering of a huge set

  6. Why are exponential-time algorithms impractical for large inputs?

    • They always produce wrong answers
    • They use exactly one memory location
    • They can only run on paper and never on any computer hardware at all
    • Their running time grows too fast to finish in a reasonable time

  7. A problem is solved by an algorithm that performs about 2^n steps for n = 50. Roughly how many steps is this?

    • About 10^15
    • About 50
    • About 10^6
    • About 10^50

  8. A computer is made twice as fast. Roughly how much larger a problem can an O(n^2) algorithm handle in the same time?

    • Twice as large
    • Four times as large
    • Exactly 2 more items
    • About 1.41 times larger

  9. Why do heuristic methods help with intractable problems?

    • They find good answers quickly, though not always the optimal one
    • They remove the need for any input
    • They guarantee the optimal answer in polynomial time for every input size
    • They make the problem tractable by definition

  10. An algorithm takes n^3 steps. Under the specification's definition, is it tractable?

    • No, because it is not exponential
    • No, because only linear algorithms are tractable
    • Yes, because it is polynomial
    • Yes, but only for odd n

  11. Which factor besides the choice of algorithm limits what computation can achieve?

    • The number of colours in the interface
    • The font used in the output
    • The length of the variable names
    • The hardware speed and memory available

  12. A brute-force search over 20 cities for a shortest tour checks roughly (n - 1)! / 2 tours. Which is the best estimate?

    • About 10^30
    • About 10^3
    • About 10^17
    • About 10^8

  13. Which statement about computing with polynomial and exponential time is correct?

    • Polynomial and exponential times grow at the same rate
    • Exponential algorithms are always faster than polynomial ones
    • Polynomial-time algorithms are practical for large n in a way exponential ones are not
    • Polynomial time only applies to graphs

  14. Why is it not enough for an intractable problem to be solved on a faster computer?

    • Faster computers cannot run any program at all, so the speed of hardware is irrelevant
    • Intractable problems must be solved on paper
    • Hardware speed is irrelevant to every problem
    • Exponential growth outpaces any fixed speed-up, so the problem stays infeasible

  15. An algorithm takes 2^n microseconds. Roughly how long does it take for n = 60?

    • About 1 hour
    • About 1 year
    • About 1 second
    • Tens of thousands of years

  16. Which statement about tractable and intractable problems is correct?

    • Tractability depends only on the programming language used
    • The classification depends on how the time grows with problem size, not on one particular machine
    • Intractable problems are always small
    • A problem is tractable whenever a particular machine can solve it

  17. Which statement about heuristics is correct?

    • They always find the optimal solution in polynomial time
    • They are only used for sorting lists of numbers
    • They make intractable problems tractable by definition
    • They trade guaranteed optimality for speed on hard problems

  18. Which problem is a good candidate for a heuristic approach?

    • Printing the first ten integers
    • Finding a near-optimal delivery route for many cities
    • Adding two single-digit numbers together
    • Reading one value from a fixed array index in constant time without any searching

  19. Which of these is an example of an intractable problem?

    • Sorting a list with merge sort, which takes about n log n steps for n items
    • Reading a file line by line
    • Finding every subset of n items and testing each one
    • Finding the maximum of a list

  20. An algorithm that runs in polynomial time is described as:

    • Exponential
    • Intractable
    • Tractable
    • Non-computable

All AQA Computer Science quizzes