Given 2 finite sets S and M, with card(S) >= card(M), and an item z not in M. There is an unknown function f: S --> M u {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) != z). The goal is to find f. To this end, I can query an oracle by sending it a question Q subset of S, and getting back from it answer A = f(Q) subset of M u {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?
Mapping problem reminiscent of Mastermind
sakuragaoka2001
- 33
- 4