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 se| A ∩ S | = | B ∩ S. Observe que seem seguida, o adversário lata de saída, quer ou .
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.
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 .
Qualquer indicação de algo relacionado seria apreciada.
Respostas:
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 < b ≤ n . 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.
fonte
... 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:
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 .
fonte