December 4, 2007

Solving Intractable Problems

Posted by Ben Simo

"A solution to a given problem is called optimal if one can prove that no better solution exists. Some skeptics might ask, Why should intuition rely on a rule of thumb instead of the optimal strategy? To solve a problem by optimization -- rather than by a rule of thumb -- implies both that an optimal solution exists and that a strategy exists to find it. Computers would seem to be the ideal tool for finding the best solution to a problem. Yet paradoxically, the advent of high-speed computers has opened our eyes to the fact that the best strategy often cannot be found." - Gerd Gigerenzer, Gut Feelings: The Intelligence of the Unconscious

An intractable problem is a problem for which there is no efficient means of solving. These aren't necessarily problems for which there is no solution. Instead, these are problems that take too long to analyze all the options.

One of the biggest challenges in testing software is to select useful tests from infinite options. Even finite sets of options can create intractable problems.

For example, state model-based test automation generally requires creation of an explicit finite model. Models are less complex than the real thing -- if they aren't, they are copies, not models. Model-based test automation can be used to generate and execute tests for many more paths through a computer program than people are willing or able to try. However, testing all paths in a model for a non-trivial program can easily become an intractable problem.

Gerd Gigerenzer demonstrates this with a challenge in his book Gut Feelings. Gigerenzer asks readers to find the shortest route to visit 50 cities starting and ending at the same city. Think you can find the solution? There are only 12 different routes to visit 5 cities. So how many combinations would you need to check to visit 50 cities? According to Gigerenzer, there are approximately 300,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 possible routes to visit 50 cities. Even with the help of computers, we do not have the time to calculate the best route.

Even relatively simple computer programs have significantly more data and path possibilities -- especially when we consider retracing paths as part of a larger path. There are potentially infinite path possibilities though even the simplest programs. (As I type each letter of this article into my computer, I am selecting an input from many more than 50 options.)

The problem of visiting 50 cities is solvable if we do not insist on finding the shortest route. Finding the shortest route and trying every possible path through a computer program are not really required to find a satisfactory solution.

Intractable problems like this require that we not consider all possibilities. Trying to consider all the options distracts us from what could be productive testing. Instead of considering all options, we only need to consider enough options to be satisfied. Otherwise, we will spend more time analyzing the possibilities than we do testing. Sometimes we just need to stop analyzing and go with our gut feelings.

"Gut feelings are based on surprisingly little information that makes them look untrustworthy in the eyes of our superego, which has internalized the credo that more is always better. Yet experiments demonstrate the amazing fact that less time and information can improve decisions. Less is more means there is some range of information, time, or alternatives where a smaller amount is better ..." - Gerd Gigerenzer, Gut Feelings: The Intelligence of the Unconscious

Gut feelings -- this unconscious thinking -- is based on heuristics, or rules of thumb. A heuristic is a problem solving device that helps narrow intractable problem into solvable problems. Heuristics are not laws. They do not apply to all situations. Two or more useful heuristics may even contradict one another. Gigerenzer states that the value of a heuristic is dependent on the context in which it is applied.

I have encountered many good testers that just seem to have a gift for breaking software. I once thought that this gift was something that could not be taught to others. I was wrong. Writers like, and including, Gerald Weinberg have shown me that teaching such problem solving is possible. Testing coaches James Bach and Michael Bolton have shown me that intuitive testing can be taught.

The secret to teaching such testing is to help good testers identify the heuristics that they use while testing. Once they are identified, they can be stated in such a way that they make sense to others. Then they can be named to make them easy to remember.*

As (or after) you test, think about why you do what you do and write it down. Don't think in terms of absolutes and programmable logic. Think in terms of rules of thumb. Then give each heuristic a name. Then share it.

If you are having trouble, here is a heuristic I've found useful for starting many things:

Start with what you recognize.

Hopefully starting will trigger many more ideas that are not obvious at the start.

* For some examples, look here for a bunch of links compiled by Brian Marick.



December 05, 2007  
Martin Taylor wrote:

Hi Ben,

The book "Gut Feelings: The Intelligence of the Unconscious" that you reference in you post sounds very much like another book that I read recently: "Blink - The Power of Thinking Without Thinking" by Malcolm Gladwell (

You may want to check it out for further insights into intuitive thinking.


December 05, 2007  
Eric Jacobson wrote:


I'm embarrassed to admit I didn't hear about heuristics until I took Michael Bolton’s RST class. They’re starting to make sense though. I actually just posted two heuristics I use to solve the “intractable” problem of knowing when to stop feature testing. You can see them on the modest little blog I just launched, I hope I can give tester bloggers back a fraction of what they’ve given me.

Thanks for the great post!