O problema do conjunto de acertos (HS) é definido como segue. Seja $ (C, k $)
- $ C = \ {S_1, S_2, …, S_m \} $ coleção de subconjunto de S, ou seja, $ S_i \ subseteq S, \ forall i $
- $ k \ in \ mathbb {N} $
Queremos saber se existe $ {S} “\ subset S $ onde $ | {S} “| < k $ de modo que $ S_i \ cap S “\ neq \ emptyset $, $ i = 1,2, …, m. $
Prove que HS é Np-Completo.
Dica : Quando $ | S_i | = 2 $, HS torna-se cobertura de vértices, já sabe que está NP-completa.
Comentários
- O que você tentou? Onde você empacou? ' Ficamos felizes em ajudá-lo a entender os conceitos, mas é improvável que você consiga apenas resolver os exercícios. Você pode encontrar esta página é útil para melhorar sua pergunta.
Resposta
3SAT é reduzido para acerto Defina o problema. Dado um 3SAT $ \ phi $ tendo $ m $ cláusulas e $ n $ variáveis, defina
$$ S = \ {x_1, \ dots x_n, \ overline {x_1}, \ dots, \ overline {x_n} \} $$ $$ S_i = \ {y_1, y_2, y_3 \}, \ text {if} y_1, y_2, y_3 \ in S \ text {e} (y_1 \ lor y_2 \ lor y_3) \ text {é uma cláusula.} $$ $$ S_x = \ {x, \ overline {x} \}, \ text {para todos variável} x. $$ $$ k = n $$
Suponha que $ \ phi $ seja satisfatório, então há uma atribuição de valor verdadeiro para $ n $ variáveis. Portanto, adicione $ x $ a $ S “$ se $ x = true $, caso contrário, adicione $ \ overline {x} $ a $ S” $.
Agora, suponha que o problema de HS tenha uma solução $ S “$. Então, como para cada variável $ x $, $ S” \ cap S_x \ neq \ emptyset $, $ S “$ tem pelo menos $ n $ literais na forma $ x $ ou $ \ overline {x} $ para cada variável $ x $. Além disso, nenhum $ x $ e $ \ overline {x} $ pode pertencer a $ S “$ ao mesmo tempo, uma vez que o tamanho de $ S” $ é no máximo $ n $. Além disso, para cada cláusula $ C_i $, $ S “\ cap S_i \ neq \ emptyset $ e então para cada cláusula nós selecionamos $ y_i \ in S” \ cap S_i $, e definimos $ x = true $ se $ y_i = x $ e $ x = false $ if $ y_i = \ overline {x} $.
Comentários
- você pode mostrar uma instância positiva e uma negativa?
Resposta
É fácil mostrar que acertar Set está em NP. Uma solução só precisa exibir o conjunto H – pode-se verificar facilmente em tempo polinomial se H é do tamanho ke intercepta cada um dos conjuntos B1,…, Bm.
Nós reduzimos da cobertura do vértice. Considere uma instância do vértice problema de cobertura – gráfico G = (V, E) e um número inteiro positivo k. Nós o mapeamos para uma instância do problema do conjunto de acertos como segue. O conjunto A é o conjunto de vértices V. Para cada aresta e ∈ E, temos um conjunto Se consistindo nos dois pontos finais de e. É fácil ver que um conjunto de vértices S é uma cobertura de vértice de G se os elementos correspondentes formam um conjunto de acerto na instância do conjunto de acerto.
Comentários
- Bem-vindo ao ComputerScience @ SE. Uso interessante do símbolo especial
∈– é comum usar MathJax, permitindo, por exemplo, subscrições adequadas: $ B_1, \ dots, B_m $. - e se tamanho de Se é maior que 2? Funcionará?
Resposta
O problema do conjunto de acertos é equivalente ao problema do conjunto de cobertura, que é definido como segue:
INPUT: uma coleção C de subconjuntos de um conjunto finito S.
SOLUÇÃO: Um conjunto de cobertura para S, ou seja, um subconjunto $ C “\ subseteq C $ such que cada elemento em S pertence a pelo menos um membro de $ C “$.
Dado $ k $ existe um conjunto que cobre $ C” $ tal que $ \ vert C “\ vert \ leq k $?
Isso parece um dever de casa, então deixo você descobrir como, dada uma instância de Set Cover, você pode convertê-la em uma instância equivalente de Hitting Set.
Caso contrário, se você deseja seguir a dica, você primeiro mostra que Hitting Set in em $ NP $, que é dada uma solução que você pode verificar em tempo polinomial.
Então, você mostra que dado um gráfico $ G = (V, E) $, encontrar uma cobertura de vértice de tamanho $ k $ é equivalente a encontrar um conjunto de acerto de tamanho $ k $. Ou seja, se $ | E | = m $, você pode construir uma instância de conjunto de acerto com a mesma quantidade de conjuntos.