What would you do?
Here's an interesting question I ask people just to see how many different and creative answers I get (especially in interviews). Let's say you are on a project with a fixed budget and a fixed due date. Assuming a waterfall software development methodology, let's say that at the point you start getting builds from Dev, you find out that there are way more features to test than expected (can you say "feature creep"?). You quickly find out that although you were involved in reviewing project requirements, functional specifications, and design docs, some requirements came in late and nobody told the Test/QA team about them. So now what do you do? You have a limited time to test before the deadline and more features to test than expected.
I've heard a lot of interesting answers. Some that I don't consider great ones were things like hire some vendors to help test (remember, fixed budget, so we have no money to bring more people onto the project), slip the schedule (again, fixed date so slipping would be very, very bad), yell at the devs and the PMs for adding more requirements without telling Test (ok, my parameters in this situation don't limit you from doing that, but that's not going to solve the problem and will probably just make it worse, even though it may feel good to you at the time). :-) Of course, the answer that is the closest to reality, sorry to say, is to cut work items like writing automation, tools, or other innovations in order to get the testing done. I don’t consider any of these to be great answers.
Some of the better answers are things like ask the devs to help you test (awesome, devs should all know something about testing and this would really drive home the fact that every project is a team effort), prioritize your test cases or scenarios and only execute the high priority cases or most common scenarios (this is the most common answer and probably the easiest course of action), but people usually forget the most important part of this and that is communicating the risks (obviously if you are not going to test functionality that you initially were planning to, your project team has now incurred a risk that you must define and communicate).
Other really good answers are to shelf the newer, unexpected features until the next release or cut other features in order to make the amount of testing manageable. That would be along the lines of decreasing scope (instead of decreasing quality). Another great answer (although it sort of avoids the point of the question in determining how one deals with complex problems) is that this situation should never, ever occur. If Test/QA is not part of the engineering process from the requirements gathering phase and continues to be part of the process as changes to the requirements happen, then that is truly the problem that needs solved. Testers need to be more vocal and visible. They need to set expectations early and educate the rest of the project team on what can and cannot be done (especially within their limited time and budget). They need to build solid, trusting relationships with Dev and PM.
What does success look like? When the new requirements come in, the recipient of those requirements (a PM at Microsoft, probably called something different in other companies) needs to say "wait, I cannot accept these new requirements until I confer with Dev AND Test".