Efficiently finding key sets

Question

A few years ago I participated in German highschool computer science competition. One of the problems was this (slightly abbreviated):

A somewhat unusual electronic lock consists of $n$ switches than can be turned on ($1$) or off ($0$). For economic reasons only $k$ of these switches are actually connected to the lock, the rest are dummies. It's impossible to tell these apart. The lock opens when all $k$ connected switches are set to the right combination, regardless of the setting of the dummy switches.

If you want to open the lock without knowing the right combination, you could repeatedly setup the switches into different positions and then press open until the lock actually opens. Construct an algorithm that for a given pair $(n,k)$ finds a set of setups for all keys such that regardless of which keys are connected to the lock and of regardless what combination of those actually opens the lock, one of the setups will open the lock. Try to construct an algorithm that computes a minimal set.

The solution that I coded (which is more or less equal to the reference solution) works like this:

1. Let $S$ be the set of all setups in the output.
2. Generate $M$, a set of $m$ setups randomly where $m$ is a customizeable parameter
3. For each element of $M$, compute how many combinations it covers that were not already covered
4. Add the element of $M$ that covers the most new solutions to $S$
5. For each element of $S$, check if if you remove it from $S$, the number of solutions covered by $S$ would fall. If that is not the case, remove that setup from $S$.
6. If $S$ covers all possible combinations, terminate.

---

Can somebody explain me better ways to solve this problem? Is it possible to find a minimal set of setups in reasonable aka polynomial time (the reference solution hints that this is not possible)?

Answer 1

Your problem is discussed in the paper Efficient construction of a small hitting set for combinatorial rectangles in high dimension by Linial, Luby, Saks and Zuckerman. The object you're after is called a $(2,n,2^{-k})$-hitting set in the paper (this notation is not standard). They construct such a set of size $\mathrm{poly}(2^k\log n)$ in time $\mathrm{poly}(2^k n)$, and give a lower bound of $\Omega(2^{k+1} + \log n)$. Their construction certainly doesn't produce a minimal hitting set, and they're not necessarily interested in your range of parameters, but perhaps you could chase the literature from there on and find more relevant material.