Encontrar un conjunto por comparación de intersección

El siguiente problema surgió recientemente de mi investigación y me gustaría preguntar si alguien sabe si este problema se consideró antes o si ha oído hablar de algo que pueda estar relacionado.

La configuración general es la siguiente. Se nos ha dado $F$ , una familia de $t$ -subsets de $\{1, 2, ..., n\}$ , para algún parámetro $t$ (estoy más interesado en el caso donde $t=\lfloor n/2\rfloor$ ). Hay un adversario que recoge un conjunto de $F$ , denotado por $S$ . Nuestro trabajo es encontrar qué es $S$Para hacer esto, se nos permite enviar dos conjuntos en $F$ al adversario, digamos $A$ y $B$y el adversario generará $A$ si $|A\cap S|\geq |B\cap S|$y $B$ si $|B\cap S|\geq |A\cap S|$. Tenga en cuenta que si $|A\cap S|=|B\cap S|$entonces el adversario puede dar salida ya sea $A$ o $B$ .

Este problema se puede resolver de manera trivial si no nos importa cuántas consultas podemos hacer, ya que si comparamos todos los pares de conjuntos, $S$ será el único conjunto que el adversario siempre devuelve cuando enviamos una consulta $(S, B)$ , para cualquier $B\neq S$ . Sin embargo, nuestro objetivo es minimizar el número de consultas.

Mi objetivo es mostrar que este problema se puede resolver mediante consultas $O(poly(n))$ o que se requiere un número súper polinómico de consultas. Estoy interesado en particular en el caso en el que $F$ es el conjunto de todos $\lfloor n/2\rfloor$ -subsets de $\{1, ..., n\}$ .

Cualquier sugerencia sobre cualquier cosa relacionada sería apreciada.

Esta es una variación del famoso rompecabezas de encontrar una moneda falsificada usando la balanza . Pero antes de proceder a eso, primero resolvamos la pregunta, porque la técnica para resolverlo también es útil para ver la conexión con el problema de la moneda falsificada.

En primer lugar, supongamos que los conjuntos de consulta A y B no tienen que ser de la familia F . Luego, puede encontrar el conjunto S a lo sumo consultas de la siguiente manera. Haga consultas ({ a }, { b }) para 1≤ a < b ≤ n . Tenga en cuenta que cada elemento i ∈ {1, ..., n } se utiliza en n −1 consultas. Si un elemento i pertenece a S , entonces el conjunto { i } se responde al menos cuando el oponente no pertenece a S ($\binom{n}{2}=O(n^2)$$\binom{n}{2}$y, por lo tanto, el conjunto { i } se responde al menos n - t veces. Si un elemento i no pertenece a S , entonces el conjunto { i } no se puede responder si el oponente pertenece a S y, por lo tanto, el conjunto { i } se responde como máximo n - t −1 veces. Por lo tanto, contar cuántas veces cada conjunto se contesta, podemos determinar el conjunto S .

Esto requiere conjuntos de consultas no de la familia F , que no está permitido en el problema. Pero podemos solucionar esto agregando los mismos elementos t −1 a ambos lados. Por ejemplo, en lugar de realizar la consulta ({1}, {2}), podemos realizar la consulta ({1,3,4, ..., t +1}, {2,3,4, ..., t +1 }). Por lo tanto, el problema puede resolverse mediante consultas O ( n ² ).

Ahora comienza la parte divertida. Considere n monedas etiquetadas con 1, ..., n , yt de ellas son falsas y un poco más pesadas que las monedas reales. Todas las monedas falsas tienen los mismos pesos. Debe encontrar el conjunto S de las etiquetas de las monedas falsificadas t utilizando un saldo solo poly ( n ) veces. Cada vez que use una balanza, puede poner como máximo monedas mín. { T , n - t } a cada lado de la balanza. El equilibrio es un poco impreciso en el sentido de que si los dos lados tienen el mismo peso, cualquiera de los dos lados puede descender (de manera adversa). Como espero que puedan ver ahora, este es exactamente el mismo problema que la pregunta.

Editar : la revisión 4 y anteriores tenían un error u otro (¡ay!) En la conexión precisa con el rompecabezas de monedas falsas.

... uhm ... estoy tratando de descubrir un algoritmo polinómico ... todavía estoy trabajando en él ... pero creo que el problema debería reformularse mejor, porque hay casos en los que es imposible ganar (al menos si F es la familia de todos los subconjuntos)

Por ejemplo:

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

Como puede ver, si el adversario es un zorro , puede igualar las dos columnas, por lo que no hay forma de distinguir entre la solución y la solución ... incluso con un número exponencial de consultas.S = { 1 , 2 $S=\{1\}$$S=\{1,2\}$

Y creo que incluso si restringe a la familia F, puede "caer" en un juego imposible. Por ejemplo, agregar el elemento en algún lugar de uno o más de los conjuntos de F en el ejemplo, no matará al zorro :-)))$4$

Parece una variante del Master Mind Game, que normalmente es polinomial pero tiene una versión estática que es NP-complete ( ver prueba ).

... El juego original de Mastermind fue inventado en 1970 por Meirowitz, como un juego de mesa con agujeros para secuencias de longitud N = 4 y K = 6 clavijas de colores. Knuth (1) posteriormente mostró que esta instancia del juego Mastermind se puede resolver en cinco conjeturas o menos. Chv´atal (2) estudió la combinatoria de Mastermind general, demostrando que se puede resolver en tiempo polinómico, en el caso K> = N ... Stuckman y Zhang (3) mostraron que es NP completo para determinar si Una secuencia de conjeturas y respuestas en general Mastermind de doble cuenta es satisfactoria. ...

(1) D. Knuth. La computadora como mente maestra. Journal of Recreational Mathematics, 9: 1–5, 1977.

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

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