Wicked Problems are NP Complete

Tim O'Reilly famously encouraged software startups to focus on solving big, hard problems.  Which are sometimes referred to as "Wicked Problems", which I have written more about here and here on my "political" blog.

There is an interesting analogy between the real world wicked problems we face, and complexity theory in computer science.  In CS, some of the hardest problems are called "NP Complete", and we usually don't even attempt to solve them perfectly.  Instead, we use techniques like heuristics, and are often pleased to find a reasonable solution in a reasonable time, instead of insisting on the optimal solution, which could take longer than the expected lifespan of the universe to find.

Rihanna knows NP-complete problems can get complicated fast

I think this metaphor yields some interesting thoughts.

• In both cases we need to quickly recognize the inherent difficulty of the problem and give up on finding a perfect solution, otherwise we risk wasting precious resources.  On the other hand, even just "ok" solutions can be far more valuable than none at all.
• Solving by heuristic is quite different than solving for an exact solution.  Tackling NP-complete problems requires a very different perspective, one that gets more comfortable after spending more time on such problems.  In CS some people specialize in NP-complete problems and heuristics, and they have whole vocabularies and toolkits that are unfamiliar to those used to conventional problems.  So it is reasonable to think that dealing with wicked problems, though difficult, is an acquired skill that can be refined.



Could the many wicked problems, like NP-complete ones, be different
 faces of the same monster?  A terrifying thought, full of hope.

• In CS there are proofs that link many NP-complete problems together, essentially stating that these many different hard problems are in fact different forms of each other, and these problems can be transformed from one to another.  Finding an exact solution to one, would solve the whole bunch.  The analogous statements for Wicked Problems might be that WPs share common elements at their root, they should be considered as a set, and solving one may help solve others.  This one is by far my favourite, and made the whole analogy worthwhile IMO.