How Computability Could Help Understand Procrastination

The weather has been fine this summer for any sane-minded person to sit at home writing blogs, but today it's clear that summer has come to an end. I brewed myself a cup of coffee this morning to sulk at the rainy mist outside of my window while reading an article about how Apple is bad at design since 2013, which sent me spiral-minded to reminisce an anecdote about a boss asking me to do something to which I said is technically infeasible, and he bemoaned "you scare me when you say that." It reminded me of the introduction in Computers and Intractability book by Garey and Johnson where this poor chap has to defend himself to his boss why he can't find a tractable algorithm for a problem.

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.

I think the reason for the boss to be unimpressed throughout is that the cartoonist copied the same drawing of the boss from the previous cartoons, but he's perhaps doing it to make a point. You can't impress a boss if he doesn't get what he wants.

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.