(I imagine this would be a good interview question, but in my case it's more pragmatic than that.)
We have a large & complex application that models an extremely long and sophisticated chemical reaction process between dozens of chemical components. We are at the stage of designing Acceptance Tests for the application, but we are somewhat daunted by the intractable number of possible paths to test. It occurred to me that our situation is very much like what the Google Maps dev team must have faced when it came time to test the route-planning algorithm in their "Get Directions" feature. Obviously they couldn't test (verify and validate) every possible route. So how did they get confidence that their application would work in every situation?
And since I don't expect to find out how they did it, let me ask you: How would you go about designing a test suite with adequate code coverage, to satisfy yourself that a given application is robust -- when it is literally impossible to probe every potential path through the system?
What I'm looking for are the principles that you would use to break down an intractable problem into smaller, tractable pieces, the sum of which provide a satisfactory estimate of the whole: "I can't test everything, but I can test this, this and this -- and that's enough." I'm not looking for an approach that is "provably correct", but rather one that is prudent, given real-world budget/time constraints.
(I'm using the Google maps example as something of a foil to solicit answers that are as specific as possible.)