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. Besides hardware limitations, what fundamental factor limits what can be practical to compute?

    • Network topology
    • Compiler syntax
    • Algorithmic complexity
    • Screen resolution

  2. What time complexity threshold defines a problem as tractable?

    • Non-deterministic time
    • Exponential or more
    • Factorial time
    • Polynomial or less

  3. What defines an intractable problem in computer science?

    • No polynomial solution
    • No recursive solution
    • No constant solution
    • No linear solution

  4. What type of algorithmic problems are heuristic methods most commonly used to solve?

    • Constant-time problems
    • Linear problems
    • Non-computable problems
    • Intractable problems

  5. Which of these computational tasks is classified as a tractable problem?

    • Sorting a list
    • Boolean satisfiability
    • Halting problem
    • Travelling salesperson problem

  6. Why are algorithms with exponential time complexity considered impractical for large inputs?

    • Syntax errors occur
    • Memory addresses overflow
    • Code size increases
    • Time grows rapidly

  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. If processor speed doubles, by what factor does the manageable problem size increase for an O(n^2) algorithm?

    • 2.00
    • 4.00
    • 0.50
    • 1.41

  9. What type of approach provides approximate solutions in reasonable time for intractable problems?

    • Heuristic method
    • Exact method
    • Brute-force method
    • Recursive method

  10. How is a problem classified if its time complexity is polynomial?

    • Intractable
    • Non-computable
    • Tractable
    • Unsolvable

  11. Besides algorithmic complexity, what else limits what can be computed?

    • Compiler design
    • Programming languages
    • Database size
    • Hardware capabilities

  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. What time complexity growth rate makes a problem intractable?

    • Linear time
    • Polynomial time
    • Exponential time
    • Logarithmic time

  14. Why does upgrading hardware fail to solve intractable problems for large input sizes?

    • Constant time growth
    • Linear time growth
    • Logarithmic time growth
    • Exponential time growth

  15. What complexity classification applies to an algorithm requiring 2^n operations?

    • Polynomial time
    • Linear time
    • Constant time
    • Exponential time

  16. What property determines whether an algorithmic problem is classified as tractable or intractable?

    • Programming language used
    • Time complexity growth
    • Available RAM size
    • Processor clock speed

  17. What do heuristic algorithms sacrifice to achieve faster execution times on hard problems?

    • Polynomial complexity
    • Input size
    • Memory space
    • Guaranteed optimality

  18. Which well-known computer science problem is best solved using heuristic algorithms for large inputs?

    • Linear search
    • Travelling salesman problem
    • Binary search
    • Bubble sort

  19. What term describes a problem that cannot be solved in polynomial time?

    • Non-computable
    • Tractable
    • Intractable
    • Constant

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

    • Exponential
    • Intractable
    • Tractable
    • Non-computable

All AQA Computer Science quizzes