Skip navigation

I had big intentions to explain computational complexity in easy to understand terms to make dealing with this issue in design and verification easier. However, there is a lot of material and making it as intuitive as possible turned out to be a lot more work than I thought. Thus, no posts for a while.

In the meantime, it occurred to me that computational complexity affects our every day lives in ways that we are not aware of.  I think having some awareness these situations helps in understanding them when they are encountered it in designing complex systems.

When my son, Rory, was 1 1/2 years old, his Aunt Claire gave him a train set. If you have a boy, you probably have a train set also. Rory loved playing with this set. However, as a two-year old is apt to do, when he got frustrated, his way of taking it out was to tear up the train tracks, throwing them all over the place. Over time, we bought more and more track, which meant it took longer to do the rebuilding after each of Rory’s, um, deconstructions. After doing this numerous times, sometimes taking hours to get it just right, it dawned on me that I was solving an NP-hard problem.

NP-hard is one of those terms that you have probably heard, don’t completely understand, but believe means the problem is intractable. I will try to define it more precisely in a future post, but what I want to convey here is the intuition behind my belief that creating a track layout is NP-hard.

The goal of laying out the track is to make a loop (actually multiple interconnected loops) while using all the available track and, at the same time, minimizing the area (our house isn’t that big!). This is made more complex by the fact that there are a fixed number of different pieces, Y junctions, and bridges.

The first thing you notice when doing this is that it is easy to create a simple loop – four turns and a few straight pieces suffice. The problem, of course, is that this is not very interesting and you still have 90% of the pieces left over. It is also easy to use all the pieces if you don’t mind that the loop doesn’t close. You can just make one long chain of track. When Rory was old enough to know how to connect the track together, this is exactly what he did. It looked like we had a giant insect in the middle of our room. This illustrates one of the characteristics of NP-hard problems. Even though the problem (creating a track layout) is hard in general, there can be instances of the problem that are easy to solve.

The next you notice is that, you get an idea for a layout, start to build it and then, at the end, you find you are one piece short. You try to find  a piece by shortening the circuit somewhere else. This may entail making changes in other places also, which requires changing yet another place, and so on. More than a few levels of this and you quickly get lost and forget what the original problem was. At this point, you give up and start making wholesale changes, often running into the same problem.

This illustrates two issues that are at the crux of matter. First, you generally don’t figure out that a layout is going to work or not until it is completely built, or nearly so. Second, while it is sometimes possible to fix a layout by making incremental changes, it is often the case you cannot, which means starting from scratch again. The key here is that when we try a given configuration and it doesn’t work and we can’t fix it by making some incremental changes, we haven’t learned what a good configuration is, only that the current one is a bad one. In the worst case, then,  we would have to try every possible track configuration to find one that met our requirement of using all pieces, in a loop, and with minimum area. This is pretty much the definition of intractable.

Contrast this with a problem that is tractable, such as sorting. Suppose we have an almost sorted list. It’s never the case that we would have to start all over. The closer the list is to being sorted, the less time it takes to get it completely sorted.

The last observation that indicates that this problem is NP-hard is due to our desire to minimize the area of the resulting track layout. It is actually computationally tractable to meet the requirement of producing a loop using all available track. We can just make one giant loop. Even this is tedious, but the problem is  it would be much too large to fit in the room. Our goal is to minimize the area so that we can actually, you know, live in our living room. It turns out that the less area we want to use, the harder it is to figure out a layout. Also, it is all but impossible to determine what the minimum sized layout that meets our requires would be. These are both hallmarks of NP-hard problems. In practice, because it is impossible to determine what the minimum sized solution is, usually a limit is specified. As long as the solution produces a result less than (or greater, depending on the problem being solved) the limit, the solution is deemed a satisfying solution. When an NP-hard problem has a limit specified like this, it is called an NP-complete problem.

I hope this helps in understanding computational complexity. I will write more later. I doubt this helps in understanding how to raise kids.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: