Given 2 finite sets $S$ and $M$, with $\operatorname{card}(S) \geq \operatorname{card}(M)$, and an item $z \not\in M$. There is an unknown function $f: S \to M \cup \{z\}$, which is known to be one-to-one for all $s \in S$ for which $f(s) \in M$ (i.e. for which $f(s) \neq z$). The goal is to find $f$. To this end, I can query an oracle by sending it a question $Q \subseteq S$, and getting back from it answer $A = f(Q) \subseteq M \cup \{z\}$. Obviously, I could use the trivial strategy and sequentially ask the questions $Q = \{s\}$ over all $s \in S$, but querying the oracle is very costly. Is there a questioning strategy that is less costly than the trivial one? Or can one prove that there is no strategy less costly than the trivial one?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
Since $S$ is finite, we can label its elements $s_1, s_2, \ldots, s_n$. Then take as query sets $S_1 = \{ s_i \mid i \,\&\, 1 = 1 \}$ where $\&$ represents bitwise conjunction; $S_2 = \{ s_i \mid i \,\&\, 2 = 2 \}$, $S_k = \{ s_i \mid i \,\&\, 2^{k-1} = 2^{k-1} \}$. This gives $\lceil \lg \operatorname{card}(S) \rceil$ queries. Then the element of $S$ which maps to $m \in M$ can be found by taking the bitwise disjunction of the powers of 2 from the queries whose answers contained $m$.
answered Jul 29, 2021 at 23:34
-
$\begingroup$ This is humbling! I spent so much time trying to solve this problem while the solution couldn't be simpler. Thank you. What's the bigger theory behind it? $\endgroup$ Commented Jul 31, 2021 at 5:10
-
$\begingroup$ Is this somehow related to the Walsh-Hadamard transformation? $\endgroup$ Commented Jul 31, 2021 at 5:35
-
$\begingroup$ @sakuragaoka2001, I think of it as information theory: the basic motivating principle is how to maximise the information gained from each query. I'm not aware of a link to Walsh-Hadamard, but that doesn't mean that there isn't one. $\endgroup$ Commented Jul 31, 2021 at 8:00
-
$\begingroup$ Yes I have come that far, too. I figured that when my queries contain half of the switches, the information gain is greatest. However, there are zillions of ways to put such information-maximizing queries into a query sequence. So, what was your guiding principle to select exactly the one you suggested? $\endgroup$ Commented Jul 31, 2021 at 8:26
-
$\begingroup$ @sakuragaoka2001, I first considered divide-and-conquer. Denote the problem of determining the mapping from $S$ to $M$ as $P(S, M)$. After the first query $Q_1 \subseteq S$ with response $A_1$ we can split the problem into $P(Q_1, A_1)$ and $P(S \setminus Q_1, M \setminus A_1)$. Then the key insight is that in tackling the two subproblems we can combine a query from each, because they're disjoint, so that the second query and response splits the original problem into four disjoint subproblems, and so on. $\endgroup$ Commented Jul 31, 2021 at 8:43