Just Enough Tests

Software has too many cases to test them all. A few dozen settings combine into billions of configurations; a handful of features interact in countless ways. You can't run every test — your CI pipeline would never finish, and your bill would be enormous.

So you choose. Each test you could run covers some set of requirements — code paths, feature combinations, edge cases. The goal: pick the fewest tests that together cover every requirement. Run those, skip the rest, and you've kept your safety net while slashing time and cost.

That's optimal test selection, and it's the set-cover problem wearing a QA hat: cover a universe of requirements with as few "sets" (tests) as possible. And, like set cover, it's NP-hard.

Try it. The grid shows which requirements each test covers. Click tests to add them to your suite; covered requirements light up green. Cover all of them using as few tests as you can.

<p class="hint">{{hint}}</p>
<table class="cov" id="cov"></table>
<div class="meter">
  <div>{{tests_chosen}} <b id="count">0</b></div>
  <div id="status" class="status"></div>
</div>
<div class="btns">
  <button id="min" type="button">{{btn_minimize}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.hint .g { color: #0a7d33; font-weight: 700; }
.cov { border-collapse: collapse; }
.cov th, .cov td { border: 1px solid #e2e6eb; width: 38px; height: 34px; text-align: center; font: 600 13px system-ui; }
.cov th.req { background: #f6f8fa; color: #777; }
.cov th.req.done { background: #e6f6ec; color: #0a7d33; }
.cov th.tname { background: #fff; color: #1d3557; cursor: pointer; width: 56px; font-weight: 800; }
.cov tr.sel th.tname { background: #457b9d; color: #fff; }
.cov td { cursor: pointer; color: #cdd9e2; }
.cov td.has { color: #2a9d8f; font-weight: 800; }
.cov tr.sel td.has { background: #e6f6ec; }
.meter { display: flex; gap: 1.4rem; align-items: center; margin: .8rem 0 .6rem; font-size: 1rem; flex-wrap: wrap; }
.meter b { color: #1d3557; }
.status { font-weight: 800; }
.status.ok { color: #0a7d33; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

// Code not found

When everything's green, check your count, then hit Minimize to see the smallest possible suite. The obvious "pick the test that covers the most" greedy is tempting — and usually good — but it doesn't always find the true minimum. That gap is the NP-hardness showing through.

Testing smartly runs straight into a famous hard problem:

• Checking is easy. Given a chosen suite, confirm every requirement is covered by at least one test.
• Brute force explodes. With n candidate tests there are $2^{n}$ subsets to consider — hopeless beyond small suites.
• It's set cover. Requirements are the universe; each test is a set of the requirements it covers; you want the fewest sets covering everything. Set cover is NP-hard, so this is too.
• Combinatorial testing adds a twist. To catch interaction bugs you often want every pair (or triple) of feature values tested together — building a minimal covering array is also NP-hard.
• Greedy is the workhorse. Repeatedly pick the test covering the most still-uncovered requirements. It's fast and gives a logarithmic-factor approximation — provably close, and the best you can hope for unless P = NP.
• Exact when it counts. For critical suites, integer programming finds the true minimum on moderate instances.

So optimal testing is a daily, dollars-and-minutes encounter with NP-hardness — every CI pipeline is quietly solving a set-cover problem.

Leaner test suites pay off across software and hardware:

• CI/CD cost and speed: fewer tests mean faster pipelines and lower compute bills — at scale, a huge saving.
• Regression-test selection: after a change, run only the tests that could be affected.
• Combinatorial / configuration testing: covering all feature-pair interactions with a tiny covering array.
• Hardware and chip verification: choosing test vectors that exercise all the cases.
• Safety-critical certification: proving required coverage with a justifiable, minimal suite.

Test-impact analysis and combinatorial test tools used across the industry are, under the hood, solving exactly this covering problem.

Optimal test selection is one of the most down-to-earth hard problems on this site — it's not about cosmic limits, it's about your build time and your cloud bill. Choose too many tests and you waste minutes and money; too few and a bug slips through. The sweet spot — full coverage, fewest tests — is exactly a set-cover problem, and set cover is NP-hard.

But this is the kind of hard we live with comfortably. Greedy gets you provably close, integer programming nails the optimum when it matters, and every fast, trustworthy CI pipeline is quietly winning a small battle against NP-hardness — so the tests that run are just enough, and no more.