In computer science, an algorithm is intractable when even a modestly sized problem, say a problem that involves analyzing only hundreds of items, would take all the computing power in the universe until the end of time and still won't find an answer. More formally, such algorithm is said to take an

**exponential**time to compute. If you multiply 2 times 2 times 2 and so on for just 90 times, you reach a figure \(2^{90} \approx 10^{27} \) that is bigger than the age of the universe in nanoseconds (roughly in terms of one computing cycle of a computer), and keep multiplying for 300 times, you reach a figure \(2^{300} \approx 10^{90} \) that is bigger than the number of atoms in the universe. So a problem size of 400 would not be solvable even if all the atoms in the universe were to compute until the end of time.

Several strategies were illustrated in the book what this poor chap might say to his boss.

- He could say "I can't find an efficient algorithm. I guess I'm just too dumb." The boss is unimpressed.
- He could also say "I can't find an efficient algorithm because no such algorithm is possible." But it is hard to justify why the algorithm is impossible to the still unimpressed boss.
- Finally, the chap would say "I can't find an efficient algorithm, but neither can all these famous people." Sadly, the boss is still unimpressed.

Or the chap could say to his boss, well I know there is an efficient algorithm that will give you a figure that is generally good enough but will be off by a factor of 2 in the worst case. Would you take it? This is known in computer science as an approximation algorithm.

It's not hard for common folks to understand that there are intractable problems in life, and you just have to make do with something that is good enough. You can be a perfectionist, but finding the optimal solution to a problem will keep you busily procrastinating until the end of the universe. To counter this tendency, Steve Jobs famously said "real artists ship!"

One could argue whether Apple's design ills since his passing is due to procrastination, or perhaps they took the anti-procrastination to an extreme and shipped a premature product, but it's clear that Steve Jobs and Tim Cook would take different approaches. Whereas Tim Cook would be unimpressed when his designers tell him the problems are intractable, Steve Jobs would understand what can be reasonably accomplished within a given time frame and plan accordingly.

When solving an intractable problem, one has to plan ahead: it's better to take the complete output of an approximation algorithm than to interrupt an optimal but intractable algorithm and use the incomplete output.

## No comments:

Post a Comment