I am considering a problem which seems very classic but have no idea where to find the related results. Any help or comment will be appreciated.
Given a non-empty set $S$, a set $Q$ of the subsets of $S$ and a fixed unknown element $x\in S$, we can ask only one type of questions to determine $x$: is $x$ in $A$? ($A\in Q$, which is some subset of $S$).
For example, let $S=\{1,2,3\},Q=\{\{1,2\},\{2,3\},\{1\}\},x=2$, then we can go as follows,
- ask "is $x$ in $\{1,2\}$?", get answered "yes"
- ask "is $x$ in $\{2,3\}$?", get answered "yes"
Then we know $x$ must be 2 and stop the quering process.
Now if $x\in S$ is a random variable associated with a probability function $f$ defined on $S$, what is the optimal query tree? By being optimal, I mean the query tree that has the minimal expected number of queries before determining the answer.
In fact, if $Q$ is equal to the power set of $S$, then the optimal query tree is just the Optimal Binary Search Tree. The tricky part is, what is the optimal search tree if the questions we can ask is limited to a certain set $Q$?
Surprisingly, after one day's research, I find that the case with uniform distribution was proven to be NP-complete by this paper. It is indeed a classic question as I expected before.