Limits of computation: tractable and intractable problems

How complexity and hardware limit computation, tractable and intractable problems, and a heuristic route for the robot.

A6.7Theory of computationA level25 min

Some problems have an algorithm that solves them, but the algorithm is so slow that no computer that could ever be built would finish in time. This lesson is about that first limit: problems we can solve in principle but not in practice. Module A5 gave you Big O notation for comparing algorithms; here it becomes the line between what is practical and what is not.

Two things limit computation

• Algorithmic complexity. How the time (or memory) an algorithm needs grows with the size of its input, n. This is a property of the algorithm, not the machine.
• Hardware. How many operations a second the processor can do, and how much memory there is. Faster hardware helps, but only by a fixed factor.

The two interact. A computer twice as fast lets an O(n) algorithm handle twice as much data in the same time. For an O(2ⁿ) algorithm, doubling the speed buys you exactly one more item: 2ⁿ⁺¹ is only twice 2ⁿ. No realistic improvement in hardware rescues an exponential algorithm.

How fast things grow

At a billion simple operations a second:

• n² for n = 30 is instant.
• 2ⁿ for n = 30 takes about a second; for n = 60 it takes about 36 years.
• n! for n = 20 takes about 77 years; for n = 30 it is over 500,000 times the age of the universe.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import math

SPEED = 1e9                      # operations per second
YEAR = 60 * 60 * 24 * 365.25     # seconds in a year
for n in [10, 20, 30, 40, 60]:
    seconds = 2 ** n / SPEED
    print(f"n={n:2}  2^n takes {seconds:.3g} s = {seconds / YEAR:.3g} years")

Run this in the simulator

Tractable and intractable

A problem is tractable if it has an algorithm that solves it in polynomial time or better: O(1), O(log n), O(n), O(n log n), O(n²), O(n³) and so on. Searching, sorting and shortest paths with Dijkstra's algorithm are tractable.

A problem is intractable if it can be solved, but no polynomial-time algorithm for it is known: every known algorithm takes exponential or factorial time, such as O(2ⁿ) or O(n!). For small inputs an intractable problem is fine; the trouble is that the time explodes as n grows. Whether fast algorithms for the famous intractable problems might exist is one of the great open questions in computer science, and most computer scientists believe they do not.

Classic intractable problems:

• The travelling salesman problem: visit every one of n places once by the shortest route.
• Knapsack and bin packing: fit items of different sizes into a limited space as well as possible.
• Timetabling: give every class a room and a time with no clashes.

The travelling robot

BugBot must drop something at five points A to E, starting from S. The robot does not have to come back. A brute-force algorithm tries every order: 5 choices for the first stop, 4 for the second, and so on, 5! = 120 orders. That is instant. But 15 stops is 15! orders, about 1.3 × 10¹², which takes over 20 minutes at a billion a second, and 25 stops would take hundreds of millions of years. Brute force is O(n!).

Heuristics

When a problem is intractable, a program usually settles for an answer that is good enough, found quickly. A heuristic is a rule of thumb that finds a good solution in reasonable time but is not guaranteed to find the best one.

The nearest neighbour heuristic for the travelling robot: from where you are, always go to the closest place not yet visited. For n places it checks at most n distances for each of n steps, so it is O(n²): tractable.

From S the nearest point is E, so the heuristic goes there first, then A, B and C, and is left with a long trip back to D. Total 198.5 cm. Brute force finds that visiting D first, the one that was not quite the nearest at the start, gives 150.8 cm. The heuristic was about 30% worse here, but for 1000 drop points it still answers in a blink, while brute force would never finish.

Other heuristic methods include improving a route by swapping pairs of stops while that makes it shorter, and the A* search you met in module A5, which uses an estimate of the distance left to decide what to explore first. Satellite navigation, delivery scheduling and exam timetabling all rely on heuristics.

Task: the delivery route

Plan and drive a route to all five drop points, using the heuristic, and compare it with the best route.

• The drop points are in drops: a dictionary from a letter to an (x, y) position on the mat in cm. The robot starts at START. Distances are straight lines: use math.dist.
• drive_to(x, y) is written for you: it slides the robot to that mat position.
• Write tour_length(order): order is a sequence of letters; return the total distance from START through each point in that order, without coming back.
• Write nearest_neighbour(): return a list of the five letters in the order the nearest neighbour heuristic visits them, starting from START.
• Print nearest neighbour: then the letters separated by single spaces, a space, then the length to 1 decimal place and cm. For example nearest neighbour: A B C D E 123.4 cm.
• Find the shortest order by brute force over every order (itertools.permutations) and print it the same way, starting best:.
• Then drive the nearest neighbour route, visiting the points in that order.

Do not type any orders or lengths in; work them out.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import math
from itertools import permutations

START = (50, 10)
drops = {"A": (80, 45), "B": (65, 70), "C": (85, 85), "D": (20, 20), "E": (55, 35)}

def wrapped(h):
    return (h + 180) % 360 - 180

def drive_to(x, y, speed=70):
    # slide to the mat point (x, y), holding heading 0, until within 3 cm
    while True:
        px, py = position()
        dx, dy = x - START[0] - px, y - START[1] - py
        if math.hypot(dx, dy) < 3:
            break
        a = math.radians(wrapped(math.degrees(math.atan2(dx, dy)) - heading()))
        drive(speed * math.cos(a), speed * math.sin(a), wrapped(0 - heading()) * 3)
        wait(0.1)
    stop()

Challenges

1. How many orders would brute force try for 10 drop points? Time your program with 8 points.
2. Improve the nearest neighbour route: try swapping every pair of stops and keep any swap that shortens it. Is the result always the best route?
3. Explain why a computer a million times faster still could not use brute force for 30 drop points.