What To Test When You Can't Test It All

A naive approach to testing is to just cover everything.  I once saw a testing expert claim something like: "We figured out that all bugs occur in state transitions, so if we just test all of the state transitions, we'll find all of the bugs."  Fascinating, but not very useful.  Simple statistics says that testing all of the state transitions for even a simple program becomes intractable quickly.  Complexity theory also states fairly authoritatively that testing all branches is not possible in a reasonable period of time.  Indeed, exhaustive testing is an NP-Complete problem.  So, what are we, as testers, to do?  Cover as much as possible and hope that nothing goes bad in the other places?  That's usually the approach.  There is another method though.  Based on some studies, it has become accepted that the vast majority of bugs happen at the intersection of two variables.  Thus, we can get thorough-enough testing by testing each of these pairs.  Keith Vanden Eynden has a good article discussing the idea and its implementation.