<p>... 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 <strong>it is impossible to win</strong> (at least if F is the family of all subsets)</p>

<p>For example: </p>

<pre><code>Let n=3

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

Queries     S={1}    S={1,2}
{1}&gt;={2}      T      lie
{1}&gt;={3}      T       T
{2}&gt;={1}      F      lie 
{2}&gt;={3}     lie      T
{3}&gt;={1}      F       F
{3}&gt;={2}     lie      F
{1}&gt;={2,3}    T      lie
{2}&gt;={1,3}    F      lie
{3}&gt;={1,2}    F       F
{2,3}&gt;={1}    F      lie
{1,3}&gt;={2}    T      lie 
{1,2}&gt;={3}    T       T
</code></pre>

<p>As you can see - <strong>if the adversary is a fox</strong> - 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.</p>

<p>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, <em>will not kill the fox</em> :-)))</p>

<hr>

<p>It looks like a variant of the <a href="http://en.wikipedia.org/wiki/Mastermind_%28board_game%29" rel="nofollow">Master Mind Game</a> which normally is polynomial but has a <strong>static version</strong> which is NP-complete (<a href="http://newton.case.edu/papers/mastermind.pdf" rel="nofollow">see proof</a>).</p>

<p><em>... 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. ...</em></p>

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

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

<p>(3) J. Stuckman and G.-Q. Zhang. Mastermind is np-complete, 2005.
<a href="http://arxiv.org/abs/cs/0512049" rel="nofollow">http://arxiv.org/abs/cs/0512049</a>.</p>

CC BY-SA 2.5
2011-02-07T18:24:31.827Z
@Vor: Can Master Mind be reduced to this problem?
Marcus Ritt
CC BY-SA 2.5
2011-02-07T20:05:36.467Z
@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.
Dan
CC BY-SA 2.5
2011-02-07T21:59:06.820Z
@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.
Dan
CC BY-SA 2.5
2011-02-07T22:18:20.413Z
@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?
Marzio De Biasi
CC BY-SA 2.5
2011-02-07T22:29:20.693Z
... (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).
Marzio De Biasi
CC BY-SA 2.5
2011-02-07T23:09:57.820Z
@Vor: The running time of the algorithm could be polynomial in $N$ but my question is whether the number of queries is polynomial in $d$ or not.
Dan
CC BY-SA 2.5
2011-02-07T23:28:34.887Z
Sorry, when I said $d$, I meant $n$, the size of the universe. I guess you used $N$ to denote $|F|$.
Dan
CC BY-SA 2.5
2011-02-07T23:57:24.130Z
Ok, everything seems well defined now (to me)! In the main problem you use "t-subsets", but I think a better reformulation is: "Given the family F of subsets of {1,...,n} having size t (t<=n) ...". Tomorrow I'll try to solve it! :-)
Marzio De Biasi
CC BY-SA 2.5
2011-02-08T18:12:07.047Z
@Danu ... I think that the problem cannot be solved in poly(t)!, check my answer above (and see if it is correct).
Marzio De Biasi
CC BY-SA 2.5
2011-02-08T20:13:40.787Z
In the answer, you write “I think this is a sufficient proof that in the worst case O(n^t) queries are required to solve the problem,” but that is not true.  It only proves that you cannot answer the set S correctly if you make exponentially many queries in some bad way.  It does not rule out the possibility that you can answer S correctly if you make polynomially many queries in some _good_ way.  It is indeed possible; see my answer.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-07T18:17:07.743Z
2011-02-08T21:42:14.470Z
2011-02-08T21:42:14.470Z
Marzio De Biasi
<p>This is a variation of the <a href="http://en.wikipedia.org/wiki/Balance_puzzle">famous puzzle of finding a counterfeit coin by using the balance</a>.  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.</p>

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

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

<p>Now fun part begins.  Consider <i>n</i> coins labeled 1,…,<i>n</i>, and <i>t</i> 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 <i>S</i> of the labels of the <i>t</i> counterfeit coins by using a balance only poly(<i>n</i>) times.  Every time you use a balance, you can put at most min{<i>t</i>, <i>n</i>−<i>t</i>} 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.</p>

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

CC BY-SA 2.5
2011-02-08T18:59:04.283Z
This answers my question nicely! Thanks for the connection to the counterfeit coin problem as well.
Dan
CC BY-SA 2.5
2011-02-08T19:47:26.183Z
@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) ?
Marzio De Biasi
CC BY-SA 2.5
2011-02-08T19:57:08.103Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T20:05:54.303Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T20:13:45.737Z
@Tsuyoshi ... your algorithm starts from scanning couples of elements (augmented witth "shared" t-1 elements to match problem requirements) ... but if t=2 it is the same as "fix a shared element" ...
Marzio De Biasi
CC BY-SA 2.5
2011-02-08T20:23:55.130Z
@Vor: No, it is not equivalent to fixing a shared element.  The problem is with “fixing.”  For example, the query ({1},{2}) becomes ({1,3},{2,3}) after augmenting {3}, and the query ({3},{4}) becomes ({1,3},{1,4}) after augmenting {1}.  In general, you cannot “fix” t−1 elements to augment, because if you do that, you cannot obtain any information about the shared elements.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T20:30:44.087Z
... for example if I start with the queries: Q(12,13), Q(12,14), Q(13,12), Q(13,14), Q(14,12), Q(14,13) (see my table), in the case of solution S={1,2} the element 2 (in the solution) can be returned two times, but also the element 3 can be returned two times (two lies)!
Marzio De Biasi
CC BY-SA 2.5
2011-02-08T20:42:23.290Z
@Vor: The algorithm described in this answer will not ask those six questions.  You should really first understand the 2nd paragraph (which describes an algorithm for a relaxed version of the problem), and then proceed to the next paragraph (which describes how to convert the algorithm for the relaxed version of the problem to an algorithm for the problem in question).  Well, that is of course if you want to understand how the algorithm works.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T20:45:26.393Z
@Vor: FYI, for n=4 and t=2, the first algorithm (for the relaxed problem) makes the following six queries using your notation: Q(1,2), Q(1,3), Q(1,4), Q(2,3), Q(2,4), Q(3,4).  The second  algorithm (for the real problem) may make the following six queries: Q(13,23), Q(12,32), Q(12,42), Q(21,31), Q(21,41), Q(31,41).
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T21:40:07.670Z
@Tsuyoshi GREAT! Thank you, now I can understand it! But do you think my comment on the case where the subsets can have different sizes (some problems may be unsolvable), is correct?
Marzio De Biasi
CC BY-SA 2.5
2011-02-08T22:02:48.833Z
@Tsuyoshi, @Danu If the problem is reformulated: "if $abs(|A \cap S|-|B \cap S|)<v$ then the adversary can cheat", can you tell how big $v$ can be made before making the algorithm unapplicable (or win impossible)? ... :-D
Marzio De Biasi
CC BY-SA 2.5
2011-02-08T22:56:46.667Z
Nice answer. :) (I deleted my incorrect answer which was not careful about the oracle acting adversely).
Kaveh
CC BY-SA 2.5
2011-02-08T23:21:59.437Z
@Vor: As for your comment at 21:40 UTC, I am not sure which comment you are referring to, but if F contains two sets such that one is a proper subset of another, then the set S cannot be uniquely determined in general even if we allow exponentially many queries.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T23:30:20.413Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-14T23:50:57.863Z
@Tsuyoshi I just now come to realize one possible problem with your solution. Your algorithm works perfectly fine when $F$ is a family of *all* $t$-subsets. However, I'm not sure it will work when $F$ is *any* family of $t$-subsets. In particular, querying $(A, B)$ where $|A\setminus B|=|B\setminus A|=1$ might not be possible. For example, let $F$ be a family of $(n/4)$-subsets where the pairwise intersection size is at most $n/8$. There exists $F$ such that $|F|=2^{\Omega(n)} (see http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf). For this case, the above type of queries won't work. Any comment?
Dan
CC BY-SA 2.5
2011-02-15T00:04:39.323Z
@Danu: I assumed that F is the family of all t-subsets.  In other cases, I do not know the solution.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-08T18:27:27.947Z
2011-02-08T19:54:26.920Z
2011-02-08T19:54:26.920Z
Tsuyoshi Ito
<p>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. </p>

<p>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$. </p>

<p>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. </p>

<p>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\}$.</p>

<p>Any pointers to anything related would be appreciated. </p>

CC BY-SA 2.5
2011-02-07T19:45:34.530Z
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?
mjqxxxx
CC BY-SA 2.5
2011-02-07T19:54:35.897Z
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'$.
mjqxxxx
CC BY-SA 2.5
2011-02-07T21:13:17.437Z
@mjqxxxx: Thanks for both of your comments. I've rephrased the question to make it clearer.
Dan
<cc.complexity-theory><communication-complexity><coding-theory><query-complexity>
Finding out a set by intersection comparison
Dan
# Finding out a set by intersection comparison

(Asked by: username_0 on 2011-02-07)

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.

**Tags:** cc.complexity-theory, communication-complexity, coding-theory, query-complexity
> **Comments:**
> **username_1**: 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?  
> **username_1**: 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'$.  
> **username_0**: @mjqxxxx: Thanks for both of your comments. I've rephrased the question to make it clearer.  

---

## 2 answers

### Answer by username_4 on 2011-02-08. Score: 10 | Accepted answer

This is a variation of the [famous puzzle of finding a counterfeit coin by using the balance](http://en.wikipedia.org/wiki/Balance_puzzle). 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*<*b*≤*n*. 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 *n*−*t* 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 *n*−*t*−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(*n*2) 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*, *n*−*t*} 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.

> **Comments:**
> **username_0**: This answers my question nicely! Thanks for the connection to the counterfeit coin problem as well.  
> **username_2**: @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) ?  
> **username_4**: @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.  
> **username_4**: @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.  
> **username_2**: @Tsuyoshi ... your algorithm starts from scanning couples of elements (augmented witth "shared" t-1 elements to match problem requirements) ... but if t=2 it is the same as "fix a shared element" ...  
> **username_4**: @Vor: No, it is not equivalent to fixing a shared element.  The problem is with “fixing.”  For example, the query ({1},{2}) becomes ({1,3},{2,3}) after augmenting {3}, and the query ({3},{4}) becomes ({1,3},{1,4}) after augmenting {1}.  In general, you cannot “fix” t−1 elements to augment, because if you do that, you cannot obtain any information about the shared elements.  
> **username_2**: ... for example if I start with the queries: Q(12,13), Q(12,14), Q(13,12), Q(13,14), Q(14,12), Q(14,13) (see my table), in the case of solution S={1,2} the element 2 (in the solution) can be returned two times, but also the element 3 can be returned two times (two lies)!  
> **username_4**: @Vor: The algorithm described in this answer will not ask those six questions.  You should really first understand the 2nd paragraph (which describes an algorithm for a relaxed version of the problem), and then proceed to the next paragraph (which describes how to convert the algorithm for the relaxed version of the problem to an algorithm for the problem in question).  Well, that is of course if you want to understand how the algorithm works.  
> **username_4**: @Vor: FYI, for n=4 and t=2, the first algorithm (for the relaxed problem) makes the following six queries using your notation: Q(1,2), Q(1,3), Q(1,4), Q(2,3), Q(2,4), Q(3,4).  The second  algorithm (for the real problem) may make the following six queries: Q(13,23), Q(12,32), Q(12,42), Q(21,31), Q(21,41), Q(31,41).  
> **username_2**: @Tsuyoshi GREAT! Thank you, now I can understand it! But do you think my comment on the case where the subsets can have different sizes (some problems may be unsolvable), is correct?  
> **username_2**: @Tsuyoshi, @Danu If the problem is reformulated: "if $abs(|A \cap S|-|B \cap S|)<v$ then the adversary can cheat", can you tell how big $v$ can be made before making the algorithm unapplicable (or win impossible)? ... :-D  
> **username_5**: Nice answer. :) (I deleted my incorrect answer which was not careful about the oracle acting adversely).  
> **username_4**: @Vor: As for your comment at 21:40 UTC, I am not sure which comment you are referring to, but if F contains two sets such that one is a proper subset of another, then the set S cannot be uniquely determined in general even if we allow exponentially many queries.  
> **username_4**: @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.  
> **username_0**: @Tsuyoshi I just now come to realize one possible problem with your solution. Your algorithm works perfectly fine when $F$ is a family of *all* $t$-subsets. However, I'm not sure it will work when $F$ is *any* family of $t$-subsets. In particular, querying $(A, B)$ where $|A\setminus B|=|B\setminus A|=1$ might not be possible. For example, let $F$ be a family of $(n/4)$-subsets where the pairwise intersection size is at most $n/8$. There exists $F$ such that $|F|=2^{\Omega(n)} (see http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf). For this case, the above type of queries won't work. Any comment?  
> **username_4**: @Danu: I assumed that F is the family of all t-subsets.  In other cases, I do not know the solution.  

---

### Answer by username_2 on 2011-02-07. Score: 2

... 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.

> **Comments:**
> **username_3**: @Vor: Can Master Mind be reduced to this problem?  
> **username_0**: @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.  
> **username_0**: @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.  
> **username_2**: @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?  
> **username_2**: ... (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).  
> **username_0**: @Vor: The running time of the algorithm could be polynomial in $N$ but my question is whether the number of queries is polynomial in $d$ or not.  
> **username_0**: Sorry, when I said $d$, I meant $n$, the size of the universe. I guess you used $N$ to denote $|F|$.  
> **username_2**: Ok, everything seems well defined now (to me)! In the main problem you use "t-subsets", but I think a better reformulation is: "Given the family F of subsets of {1,...,n} having size t (t<=n) ...". Tomorrow I'll try to solve it! :-)  
> **username_2**: @Danu ... I think that the problem cannot be solved in poly(t)!, check my answer above (and see if it is correct).  
> **username_4**: In the answer, you write “I think this is a sufficient proof that in the worst case O(n^t) queries are required to solve the problem,” but that is not true.  It only proves that you cannot answer the set S correctly if you make exponentially many queries in some bad way.  It does not rule out the possibility that you can answer S correctly if you make polynomially many queries in some _good_ way.  It is indeed possible; see my answer.  

---

