8
$\begingroup$

The following problem recently emerged from my research and I would like to ask if anyone knows if this problem was considered before or has heard of anything that might be related.

The general setting is the following. We are given $F$, a family of $t$-subsets of $\{1, 2, ..., n\}$, for some parameter $t$ (I am most interested in the case where $t=\lfloor n/2\rfloor$). There is an adversary who picks one set in $F$, denoted by $S$. Our job is to find what $S$ is. To do this, we are allowed to send any two sets in $F$ to the adversary, say $A$ and $B$ and the adversary will output $A$ if $|A\cap S|\geq |B\cap S|$ and $B$ if $|B\cap S|\geq |A\cap S|$. Note that if $|A\cap S|=|B\cap S|$ then the adversary can output either $A$ or $B$.

This problem can be solved trivially if we do not care how many queries we can ask since if we compare all pairs of sets, $S$ will be the only set that is always returned back from the adversary when we send a query $(S, B)$, for any $B\neq S$. However, our goal is to minimize the number of queries.

My goal is to show either that this problem can be solved using $O(poly(n))$ queries or that super-polynomial number of queries are required. I'm particularly interested in the case where $F$ is the set of all $\lfloor n/2\rfloor$-subsets of $\{1, ..., n\}$.

Any pointers to anything related would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ Can you clarify the "adversary can answer anything" condition? Do you mean that the answer will be either $|A\cap S| \ge |B\cap S|$ or $|B\cap S| \ge |A\cap S|$, and that since both are true when $|A\cap S|=|B\cap S|$, either answer can be given? $\endgroup$ – mjqxxxx Feb 7 '11 at 19:45
  • 1
    $\begingroup$ Why is the trivial solution correct? Surely any superset $S'$ of $S$ will also satisfy $|S'\cap S| \ge |B \cap S|$ for all $B \neq S'$. $\endgroup$ – mjqxxxx Feb 7 '11 at 19:54
  • $\begingroup$ @mjqxxxx: Thanks for both of your comments. I've rephrased the question to make it clearer. $\endgroup$ – Danu Feb 7 '11 at 21:13
10
$\begingroup$

This is a variation of the famous puzzle of finding a counterfeit coin by using the balance. But before proceeding to that, first let’s solve the question, because the technique in solving it is also useful to see the connection to the counterfeit coin problem.

First, suppose that the query sets A and B do not have to be from the family F. Then you can find the set S by at most $\binom{n}{2}=O(n^2)$ queries as follows. Make $\binom{n}{2}$ queries ({a}, {b}) for 1≤a<bn. Note that every element i∈{1,…,n} is used in n−1 queries. If an element i belongs to S, then the set {i} is answered at least when the opponent does not belong to S, and therefore the set {i} is answered at least nt times. If an element i does not belong to S, then the set {i} cannot be answered if the opponent belongs to S, and therefore the set {i} is answered at most nt−1 times. Therefore, counting how many times each set is answered, we can determine the whole set S.

This requires query sets not from the family F, which is not allowed in the problem. But we can work around this by adding the same t−1 elements to both sides. For example, instead of making the query ({1}, {2}), we can make the query ({1,3,4,…,t+1}, {2,3,4,…,t+1}). Therefore, the problem can be solved by O(n2) queries.

Now fun part begins. Consider n coins labeled 1,…,n, and t of them are counterfeits and slightly heavier than the real coins. All the counterfeit coins have the same weights. You have to find the set S of the labels of the t counterfeit coins by using a balance only poly(n) times. Every time you use a balance, you can put at most min{t, nt} coins to each side of the balance. The balance is slightly inaccurate in the sense that if the two sides have the same weight, either side can go down (adversarially). As I hope that you can see by now, this is exactly the same problem as the question.

Edit: Revision 4 and earlier had one error or another (oops) in the precise connection to the counterfeit coin puzzle.

$\endgroup$
  • $\begingroup$ This answers my question nicely! Thanks for the connection to the counterfeit coin problem as well. $\endgroup$ – Danu Feb 8 '11 at 18:59
  • $\begingroup$ @Tsuyoshi Great ... I thougth it was exponential! Can you show how the algorithm - in the case of n=4, t=2 ... - can discriminate in n^2 queries between solution {1,2} and solution {1,3} (see all possible queries and possible balance answers in my example) ? $\endgroup$ – Marzio De Biasi Feb 8 '11 at 19:47
  • 2
    $\begingroup$ @Vor: I think that I had stated how to do that clearly enough in the answer. If any part is unclear, I am happy to explain or rewrite it. $\endgroup$ – Tsuyoshi Ito Feb 8 '11 at 19:57
  • $\begingroup$ @Vor: That is not how the algorithm starts. I suggest you to read the answer carefully, especially the 2nd paragraph (which describes a solution to the relaxed version of the problem where query sets are not restricted to sets in F). We first make $\binom{n}{2}$ queries, and then we make decision. We do not “pick” anything until the last step. $\endgroup$ – Tsuyoshi Ito Feb 8 '11 at 20:05
  • 1
    $\begingroup$ @Vor: As for your comment at 22:02 UTC, if F is the family of all subsets of size t (1≤t≤n−1) as in the original question and the adversary can tell a lie if the absolute difference between |A∩S| and |B∩S| is at most 1, then the adversary can pretend as if S=[t] when the true answer is S=[t−1]∪{t+1}, and therefore the set S cannot be uniquely determined in general even with exponentially many queries. $\endgroup$ – Tsuyoshi Ito Feb 8 '11 at 23:30
2
$\begingroup$

... uhm ... I'm trying to figure out a polynomial algorithm ... still working on it ... but I think the problem should be better reformulated, because there are cases where it is impossible to win (at least if F is the family of all subsets)

For example:

Let n=3

F={{1},{2},{3},{1,2},{1,3},{2,3}}

Queries     S={1}    S={1,2}
{1}>={2}      T      lie
{1}>={3}      T       T
{2}>={1}      F      lie 
{2}>={3}     lie      T
{3}>={1}      F       F
{3}>={2}     lie      F
{1}>={2,3}    T      lie
{2}>={1,3}    F      lie
{3}>={1,2}    F       F
{2,3}>={1}    F      lie
{1,3}>={2}    T      lie 
{1,2}>={3}    T       T

As you can see - if the adversary is a fox - he can made the two columns equal so there is no way to distinguish between solution $S=\{1\}$ and solution $S=\{1,2\}$ .... even with an exponential number of queries.

And I think that even if you restrict the family F you can "fall" in an impossible game. For example adding the element $4$ somewhere in one or more of the sets of F in the example, will not kill the fox :-)))


It looks like a variant of the Master Mind Game which normally is polynomial but has a static version which is NP-complete (see proof).

... The original Mastermind game was invented in 1970 by Meirowitz, as a board game having holes for sequences of length N = 4 and K = 6 colored pegs. Knuth (1) subsequently showed that this instance of the Mastermind game can be solved in five guesses or less. Chv´atal (2) studied the combinatorics of general Mastermind, showing that it can be solved in polynomial time, in the K >= N case .... Stuckman and Zhang (3) showed that it is NP-complete to determine if a sequence of guesses and responses in general double-count Mastermind is satisfiable. ...

(1) D. Knuth. The computer as a master mind. Journal of Recreational Mathematics, 9:1–5, 1977.

(2) V. Chv´atal. Mastermind. Combinatorica, 3(3/4):325–329, 1983.

(3) J. Stuckman and G.-Q. Zhang. Mastermind is np-complete, 2005. http://arxiv.org/abs/cs/0512049.

$\endgroup$
  • $\begingroup$ @Vor: Can Master Mind be reduced to this problem? $\endgroup$ – Marcus Ritt Feb 7 '11 at 18:24
  • $\begingroup$ @Vor: Thanks for your answer. The master mind game looks related. I think the problem that I asked is as hard as the mastermind game (but could be harder) in the sense that your problem can be reduced to this problem (but I don't see if the converse is possible), as follows. Let's say there are just two color code, black and white. For each peg $p_i$, I can represent its color by an element (in S or not). Then, for the adversary to answer whether $|A\cap S|\geq |B\cap S|$, he can put two rows of pegs corresponding to $A$ and $B$ and look at the pegs with correct color and position. $\endgroup$ – Danu Feb 7 '11 at 20:05
  • $\begingroup$ @Vor: Before you updated your solution, I have rephrased the question to make it clearer (as @mjqxxxx commented). Now we require that all sets in $F$ have the same size so your case cannot happens. Sorry for the confusion. $\endgroup$ – Danu Feb 7 '11 at 21:59
  • $\begingroup$ @Danu ... ok ... mmm ... if every subset in F has the same size then the algorithm has complexity O(N^2): just pick the set that scores TRUE on all queries when compared to the other |F|-1 sets ?!? Or you do not consider F as the input of the algorithm? $\endgroup$ – Marzio De Biasi Feb 7 '11 at 22:18
  • $\begingroup$ ... (cannot edit comments after 5min) ... if you require that all sets of F must have the same size (including the solution), then this size must be an input parameter, unless you specify every subset of F (but in this case you fall in the trivial O(N^2) solution). $\endgroup$ – Marzio De Biasi Feb 7 '11 at 22:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.