Finding the smallest subset s.t. all elements satisfy condition, using as few tests as possible

Question

I'm having a hard time describing this problem without an example, so let's go with this: Say you have a program that is made up of many files. There are some files you could delete, and, while it might be crippled, the program could still run. We're assuming each file is independent from the others, so behind the scenes there's a subset of necessary files, and the only condition for the program to run is that none of them are missing.

You want to reduce the number of files as much as possible, by classifying all files and deleting the unnecessary ones. You can achieve this by running a trial, choosing some random subset and trying to run the program with it. If it runs, we know that none of the files we omitted are necessary files.

How can you solve this problem most efficiently, i.e., classify all files using as few trials as possible?

---

Update: A naive algorithm to solve this problem would be:

necessaryFiles = []
for each file f:
    testSet = All files except f
    if programRuns(files = testSet):
        Add f to necessaryFiles

This algorithm tests files one at a time, and thus runs in $O\left(\text{# of files}\right)$. I am looking for a way to group files into different tests that runs faster. Of note here is that simple binary search doesn't work, because we have multiple target files, and as such splitting all files between two lists doesn't guarantee one of them will contain all targets.

Answer 1

Your algorithm is a good one, about as good as you can get.

If you care about the worst-case number of tests, your algorithm is optimal. Let $n$ denote the total number of files. Then any algorithm must perform at least $n$ queries in some cases. There are $2^n$ possibilities for the final answer (since there are $2^n$ possible subsets of the $n$ files). Each test gives you only 1 bit of information. After $k$ tests, we have only $k$ bits of information; to choose among $2^n$ possibilities, we need $n$ bits of information, so you can't do better than $n$ tests, in the worst case.

If you care about the average-case number of tests, and you assume that each file has a $1/2$ probability of being necessary, then I expect that your algorithm is also optimal. In this case, there are $2^n$ possibilities for the subsets, all equally likely, so $n$ bits of information are needed, and each test gives you 1 bit of information, so on average I believe you need at least $n$ tests.

If you have some prior knowledge about the likelihood that each file is necessary, you may be able to do better. For instance, suppose you know that only about a $p$ fraction of the files are necessary, and specifically, the probability that each file is necessary is $p$, independent of all other files. I'll show one algorithm for this problem below. There may be better algorithms; I don't know. For simplicity, I'll assume $p\le 1/2$; if $p>1/2$, you can solve the problem similarly, reversing everything appropriately.

Algorithm:

1. If $p \ge 1-\sqrt{1/2} \approx 0.293$, then run the basic algorithm above, using one query per file.
2. Otherwise, set $k := \lfloor -1/\lg(1-p) \rfloor$. Randomly partition the $n$ files into $\approx n/k$ blocks of $k$ files.
3. For each block, query the set of all files except for that one block.
   • If the program still runs, then you know all the files in that block are unnecessary.
   • If the program doesn't still run, then you know that at least one file in the block is necessary, but you don't know which one(s) are necessary.
4. Set $q := p/(1 - (1-p)^k)$. Let $S$ be the set of files that are not known to be unnecessary, i.e., all the files from all the blocks where the program didn't still run. Recursively run this algorithm on $S$, but now with probability $q$ instead of $p$.

If you use this algorithm, after step 3 on average $S$ will contain $|S| \approx n(1 - (1-p)^k) \approx n/2$ files, on average about $q |S|$ of those files will be necessary, and typically we'll have $q \approx 2p$. For small $p$, if we unroll the recursion, I think we'll find that this algorithm will perform a total of about $n (h_2(p) + o(1))$ queries, where $h_2(p) = -p \lg p - (1-p) \lg (1-p)$ is the binary entropy function.

There is a matching lower bound, which says that on average you need at least $n h_2(p)$ queries. This is because the Shannon entropy of the distribution of possible sets of necessary files is about $n h_2(p)$ bits, and each query gives you at most one bit of information about this value, so you need at least $n h_2(p)$ queries on average.