# 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.