Limits of computation, tractability and heuristics

Overview

Recall questions on tractable and intractable problems, why intractable does not mean impossible, and why heuristics are used when no efficient algorithm exists.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What two things impose limits on what can be computed?

   Model answer

   Algorithmic complexity and hardware. Complexity limits what can be computed in a sensible time because an algorithm whose work grows exponentially becomes impossible to finish however it is coded. Hardware limits because any real machine has a finite processor speed, a finite amount of memory and a finite amount of storage, and the user has a finite amount of time to wait.

2. 2

   If a computer were made a thousand times faster, which limits would disappear and which would not?

   Model answer

   The hardware limit is eased but not removed: a thousand-fold speed-up multiplies the size of problem you can handle in a given time by a thousand for a linear algorithm, but only lets an O(2ⁿ) algorithm handle about ten more items, since 2¹⁰ is roughly a thousand. The limit imposed by algorithmic complexity therefore survives any realistic improvement in hardware, and problems that cannot be solved algorithmically at all are unaffected by speed entirely.

3. 3

   Define a tractable problem.

   Model answer

   A tractable problem is one that has a polynomial (or less) time solution — an algorithm whose running time grows no faster than some fixed power of the problem size, such as O(n), O(n log n) or O(n²).

4. 4

   Define an intractable problem.

   Model answer

   An intractable problem is one that has no polynomial (or less) time solution. The only known algorithms that solve it exactly take exponential time or worse, so the running time becomes impossibly long as the size of the problem grows even modestly.

5. 5

   Does intractable mean the same as impossible? Explain.

   Model answer

   No. An intractable problem can be solved — an algorithm exists and would give the right answer if it were allowed to finish — but only in a length of time that makes it useless for anything but very small inputs. This is quite different from a non-computable problem, for which no algorithm exists at all, however long it is given.

6. 6

   Give two examples of intractable problems and say why they are hard.

   Model answer

   Finding the shortest tour that visits every city once and returns to the start: checking every possible order of n cities means examining n! tours, and n! grows faster than any polynomial. Packing items of different sizes into the fewest possible bins: the number of ways of dividing the items between bins grows exponentially with the number of items. In both cases the difficulty is that the number of candidate solutions to check explodes as the problem grows, and no method is known that avoids checking them.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.