1993 United States NP-complete

Test Suite Minimization

Mary Jean Harrold, Rajiv Gupta, Mary Lou Soffa, 1993 — selecting the smallest test suite that still covers all the things you care about is NP-complete. Reduces to set cover.

Mary Jean Harrold (Clemson), Rajiv Gupta (Pittsburgh), and Mary Lou Soffa (Pittsburgh) gave the formal definition of the test suite minimization problem and proved it NP-complete by reduction from minimum set cover. Given a test suite T and a set of testing requirements R, find the smallest subset T' ⊆ T such that every requirement in R is satisfied by at least one test in T'. Each test "covers" some requirements; you want minimum number of tests that cover all requirements; this is set cover, exactly. Set cover was on Karp's 1972 list. Their paper introduced the HGS heuristic — a greedy algorithm that runs in polynomial time and gives a logarithmic approximation. Every modern test-reduction tool descends from this paper. The hardness is unavoidable; only the heuristic varies.

In plain terms

A large software project accumulates tests the way a forest accumulates leaves. Every bug fix adds a regression test. Every feature adds an acceptance test. Every refactor adds a contract test. After a few years, running the entire suite takes hours. Every team eventually faces the same question: which tests can we cut and still know we have not regressed? The formal version is sharper. Each test exercises some set of requirements — lines of code, branches, mutations, business rules. You want the smallest subset of tests that still exercises every requirement at least once. Pick too few and you stop catching bugs. Pick too many and you pay the time cost. The sweet spot is a minimum cover. Harrold, Gupta, and Soffa proved this is the set cover problem in disguise. Set cover was one of Karp's original twenty-one NP-complete problems. So test suite minimization, exactly, is NP-complete. No tool, no AI, no heuristic will solve it optimally on real codebases — the search space is too large. Their paper did the next best thing. It gave a greedy heuristic — pick the test that covers the most uncovered requirements, mark those requirements covered, repeat — and proved that greedy gives you a logarithmic approximation: at worst, ln(n) times the optimum. This is the same approximation ratio as the classic greedy set cover algorithm, and it is the best you can hope for unless P = NP. Every test-reduction tool you have ever used — Bazel test selection, Pytest sharding, every commercial regression-test optimizer — is running a variant of HGS or a refinement of it. The shape has not changed in thirty years because the underlying complexity has not changed. And the underlying complexity is not going to change, because Karp drew the floor in 1972 and that is where we live. Pick which tests to keep. NP-complete. Greedy heuristic since 1993.