Descobrir um conjunto por comparação de interseção

8

O problema a seguir surgiu recentemente de minha pesquisa e eu gostaria de perguntar se alguém sabe se esse problema foi considerado antes ou se ouviu falar de algo que possa estar relacionado.

A configuração geral é a seguinte. Nos é dado , uma família de subconjuntos de , para algum parâmetro (estou mais interessado no caso em que ). Há um adversário que escolhe um conjunto em , denotada por . Nosso trabalho é descobrir o que éPara fazer isso, podemos enviar dois conjuntos em para o adversário, digamos e e o adversário produzirá see seFt{1,2,...,n}tt=n/2FSSFUMABUMA|UMAS||BS|B| A S | = | B S|BS||UMAS|. Observe que seem seguida, o adversário lata de saída, quer ou .|UMAS|=|BS|UMAB

Esse problema pode ser resolvido trivialmente se não nos importarmos com quantas consultas poderemos fazer, pois se compararmos todos os pares de conjuntos, será o único conjunto que sempre será retornado do adversário quando enviarmos uma consulta , para qualquer . No entanto, nosso objetivo é minimizar o número de consultas.S(S,B)BS

Meu objetivo é mostrar que esse problema pode ser resolvido usando consultas ou que é necessário um número super polinomial de consultas. Estou particularmente interessado no caso em que é o conjunto de todos os -setsets de .O(poeuy(n))Fn/2{1,...,n}

Qualquer indicação de algo relacionado seria apreciada.

Danu
fonte
1
Você pode esclarecer a condição "o adversário pode responder a qualquer coisa"? Você quer dizer que a resposta será ou | B S | | A S | e que, uma vez que ambos são verdadeiros quando | A S | = | B S | , qualquer resposta pode ser dada? |UMAS||BS||BS||UMAS||UMAS|=|BS|
Mjqxxxx
1
Por que a solução trivial está correta? Certamente qualquer superconjunto de S também satisfarápara todos os . SS|SS||BS|BS
Mjqxxxx
@mjqxxxx: Obrigado por seus dois comentários. Eu reformulei a questão para torná-la mais clara.
Danu

Respostas:

10

Esta é uma variação do famoso quebra-cabeça de encontrar uma moeda falsificada usando a balança . Mas antes de prosseguir com isso, primeiro vamos resolver a questão, porque a técnica para resolvê-la também é útil para ver a conexão com o problema da moeda falsificada.

Primeiro, suponha que os conjuntos de consulta A e B não tem que ser da família F . Em seguida, você pode encontrar o conjunto S no máximo consultas da seguinte maneira. Faça consultas ({ a }, { b }) para 1≤ a < bn . Observe que todo elemento i ∈ {1,…, n } é usado em n- 1 consultas. Se um elemento i pertence a S , o conjunto { i } é respondido pelo menos quando o oponente não pertence a S(n2)=O(n2)(n2)e, portanto, o conjunto { i } é respondido pelo menos n - t vezes. Se um elemento i não pertencer a S , o conjunto { i } não poderá ser respondido se o oponente pertencer a S e, portanto, o conjunto { i } será respondido no máximo n - t -1 vezes. Portanto, contando quantas vezes cada conjunto é respondida, podemos determinar o conjunto S .

Isso requer conjuntos de consultas que não são da família F , o que não é permitido no problema. Mas podemos contornar isso adicionando os mesmos elementos t -1 nos dois lados. Por exemplo, em vez de fazer a consulta ({1}, {2}), podemos fazer a consulta ({1,3,4,…, t +1}, {2,3,4,…, t +1 }). Portanto, o problema pode ser resolvido por consultas O ( n 2 ).

Agora parte divertida começa. Considere n moedas rotuladas como 1,…, n , e t são falsificações e um pouco mais pesadas que as moedas reais. Todas as moedas falsificadas têm os mesmos pesos. Você deve encontrar o conjunto S dos rótulos das t moedas falsificadas usando uma balança apenas pol ( n ) vezes. Toda vez que você usa uma balança, você pode colocar no máximo min { t , n - t } moedas em cada lado da balança. A balança é um pouco imprecisa no sentido de que, se os dois lados tiverem o mesmo peso, ambos os lados poderão diminuir (adversamente). Como espero que você possa ver agora, esse é exatamente o mesmo problema da pergunta.

Edit : A revisão 4 e anterior tiveram um erro ou outro (oops) na conexão precisa com o quebra-cabeça de moedas falsas.

Tsuyoshi Ito
fonte
Isso responde bem à minha pergunta! Obrigado pela conexão com o problema da moeda falsificada também.
Danu
@ Tsuyoshi Ótimo ... eu pensei que era exponencial! Você pode mostrar como o algoritmo - no caso de n = 4, t = 2 ... - pode discriminar em n ^ 2 consultas entre a solução {1,2} e a solução {1,3} (veja todas as consultas possíveis e possíveis equilibrar respostas no meu exemplo)?
Marzio De Biasi
2
@Vor: Eu acho que afirmei como fazer isso com bastante clareza na resposta. Se alguma parte não estiver clara, fico feliz em explicá-la ou reescrevê-la.
Tsuyoshi Ito
@Vor: Não é assim que o algoritmo inicia. Sugiro que você leia a resposta com atenção, especialmente o segundo parágrafo (que descreve uma solução para a versão simplificada do problema em que os conjuntos de consultas não se restringem aos conjuntos em F). Primeiro criamos consultas e depois tomamos uma decisão. Não escolhemos nada até o último passo. (n2)
Tsuyoshi Ito
1
@Vor: Quanto ao seu comentário às 22:02 UTC, se F é a família de todos os subconjuntos de tamanho t (1≤t≤n-1), como na pergunta original, e o adversário pode mentir se a diferença absoluta entre A∩S | e | B∩S | é no máximo 1, então o adversário pode fingir como se S = [t] quando a resposta verdadeira é S = [t-1] ∪ {t + 1} e, portanto, o conjunto S não pode ser determinado exclusivamente em geral, mesmo exponencialmente. muitas consultas.
Tsuyoshi Ito
2

... uhm ... estou tentando descobrir um algoritmo polinomial ... ainda trabalhando nele ... mas acho que o problema deve ser melhor reformulado, porque há casos em que é impossível vencer (pelo menos se F é a família de todos os subconjuntos)

Por exemplo:

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 você pode ver - se o adversário é uma raposa - ele pode tornar as duas colunas iguais, de modo que não há como distinguir entre a solução e a solução S = { 1 , 2 } .... mesmo com um exponencial número de consultas.S={1}S={1,2}

E acho que mesmo se você restringir a família F, poderá "cair" em um jogo impossível. Por exemplo, adicionar o elemento em algum lugar de um ou mais dos conjuntos de F no exemplo, não matará a raposa :-)))4


Parece uma variante do Master Mind Game que normalmente é polinomial, mas tem uma versão estática que é NP-completa ( veja a prova ).

... O jogo Mastermind original foi inventado em 1970 por Meirowitz, como um jogo de tabuleiro com furos para sequências de comprimento N = 4 e K = 6 pinos coloridos. Knuth (1) subseqüentemente mostrou que esta instância do jogo Mastermind pode ser resolvida em cinco palpites ou menos. Chv´atal (2) estudou a combinatória do Mastermind geral, mostrando que ele pode ser resolvido em tempo polinomial, no caso K> = N .... Stuckman e Zhang (3) mostraram que é NP-completo para determinar se uma sequência de suposições e respostas em geral Mastermind de contagem dupla é satisfatória. ...

(1) D. Knuth. O computador como uma mente mestre. Journal of Recreational Mathematics, 9: 1-5, 1977.

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

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

Marzio De Biasi
fonte
@Vor: O Master Mind pode ser reduzido a esse problema?
Marcus Ritt
pEu|UMAS||BS|UMAB
Danu
F
@ Danu ... ok ... mmm ... se todo subconjunto em F tem o mesmo tamanho, o algoritmo tem complexidade O (N ^ 2): basta escolher o conjunto que obtém VERDADEIRO em todas as consultas quando comparado ao outro | Conjuntos F | -1?!? Ou você não considera F como a entrada do algoritmo?
Marzio De Biasi
... (não é possível editar comentários após 5 minutos) ... se você precisar que todos os conjuntos de F tenham o mesmo tamanho (incluindo a solução), esse tamanho deverá ser um parâmetro de entrada , a menos que você especifique todos os subconjuntos de F (mas nesse caso, você cai na solução trivial de O (N ^ 2)).
Marzio De Biasi