(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.)
Best Answer
I worked in the car navigation field over a decade ago.
Step A) Use a reference package and select a large sample set, run A/B tests. Not looking for exactness, looking for outliers - The reference set showed Reroute 1234 as 10.34km, and we calculated 123.5km.
Step B) - Refine our software and the reference software - Add more samples and reduce the tolerances.
Step C) - In house testing using local knowledge across global data sets.
Step D) UAT... "User Acceptance Test" As in "Sell this stuff and see what the customers complain about the most"
If you ever used mapping products circa Mid 1990's - 2000, you know what I mean, those of us that did still check the turn by turn directions every time.
Back to you example question. What you are being asked is how to prove that a piece of software is correct. If you want mathematical proof, it's been shown it can be done - for simple software at a price that exceeds any realistic budgets, for a complex software package, well, that is still research.... NASA has models for writing highly reliable software within economically manageable prices, as do DoD and the aviation industry - although still much higher than most are willing to pay. In the end, it comes down to how much are you prepared to pay.....
Edit : I just re-read you OP. It seems what you are looking for is a quick and cheap way to Test the quality of a complex piece of software. You cannot test in quality. You need to have a robust process so you know that what is built works correctly. If you have got to thinking about how to prove it's correct and you already have a the "large and complex application", you are too late.