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.