Andrew Prendergast

Some startup is launching a new chip tomorrow. It makes the huge claim of being able to solve an NP-complete problem. They chose a great venue - the Computer History Museum in Silicon Valley, just around the corner from the Googleplex.

Lots of computing problems are NP, generally most of the good ones. The 25 word summary is that NP problems can not currently be solved in a reasonable amount of time except when the problem is reduced to a trivial size. An example of an NP-complete problem is finding the optimal route a FedEx truck should take. Fortunately for most of these problems, fast estimations do exist.

Where NP-completeness gets interseting is that if you can solve any single NP-complete problem (such as the fedex problem), you can use that same solution to solve every other NP-complete problem - ie, solve one and you have solved them all.

If they are for real then then implications are huge, from breaking encryption to achieving artificial intelligence. I am optimistically sceptical.. lets see what happens.

ap.

Posted by ap at 01:33 PM | Permalink | Comments (1)

Yay I used a bayes decision tree to isolate a bug today in a fraction of the time it would have otherwise taken.

About 48 hours ago I started work on repairing a Heisenbug. For the less geeky of you, Heisenbugs are a rather nasty class of software fault that “disappears or alters its characteristics when it is researched”.

Most bugs are generally the result of only a single input (or knob or button or whatever) being set to a single value (or range or whatever). Software testers live by this assumption, and 99% of the time it is true, so true that we tend to forget (or is that ignore?) the 1% of bugs that can’t be explained so easily.

After tearing my hair out all yesterday and going to bed feeling somewhat defeated, this morning I woke with a fresh mind, a new day and a small suspicion that perhaps this bug fell into that 1%.

After poking and prodding at my adversary for most of the morning it was pretty clear that this was occurring probabilistically and that some pairs of input combinations made the bug occur more frequently.

Turns out the randomness was due to a threaded race condition and a combination of three inputs being in a certain range tended to make it occur more frequently – knowing those settings (which fell out of the decision tree) was thankfully enough to explain why the bug was occurring.

Posted by ap at 09:42 PM | Permalink | Comments (0)

I'm no longer at gnoos.

Working there wasn't much fun, they seemed to harness everything annoying about being a startup without any of the good stuff. I do wish them all the best but its time for me to move on.

So I guess that means I'm back in the consulting game. Fortunately the phone has already started ringing, I think this year is going to be a big one.

Posted by ap at 12:16 PM | Permalink | Comments (0)