# DRMacIver's Notebook

Deleting larger intervals in test case reduction

Deleting larger intervals in test case reduction

So here's a surprising fact I just noticed.

Suppose you've got some sequence $S$ and a predicate $p$ and you want to do test-case reduction on $S$ with respect to $p$.

Classically we try to get the result to be one-minimal. I'm pretty sure that by choosing $p$ carefully you can always force this to require ${|S|\choose 2}$ evaluations of $p$. You certainly can with the greedy algorithm. See this mathoverflow question I asked about generalising.

A stronger condition you might want is what you might call interval minimality. That is you want to find $S'$ with $p(S')$ such that $p([S_1', \ldots, S_i', S_j', \ldots, S_n'])$ is false for any $i < j$.

The funny thing is that these tasks have the same worst case complexity.

If you run the brute force algorithm that tries to delete each interval of length $k$ at a time, increasing $k$ when that fails, if you delete an interval of size $m$ then this takes you worst case $m \frac{2n - m + 1}{2}$ evaluations, but it decreases the size of the sequence by $m$. By doing induction and seeing where the maximum lies, this means that the actual number of predicate evaluations to get to a fixed point can also never exceed ${|S|\choose 2}$.

The typical case is generally not going to be as good, but it's interesting that the worst case is the same.