Reduza o seguinte problema para SAT

21

Aqui está o problema. Dado , em que cada . Existe um subconjunto com tamanho máximo de tal que para todos os ? Estou tentando reduzir esse problema para o SAT. Minha idéia de uma solução seria ter uma variável para cada um de 1 a . Para cada , crie uma cláusula se . Então e todas essas cláusulas juntas. Mas isso claramente não é uma solução completa, pois não representa a restrição de quek,n,T1,,TmS { 1 , ... , n } k S t ii x i n t i ( x i 1Ti{1,,n}S{1,,n}kSTiixinTiT i = { i 1 , ... , i k }(xi1xik)Ti={i1,,ik}Sdeve ter no máximo elementos. Eu sei que preciso criar mais variáveis, mas simplesmente não sei como. Então, eu tenho duas perguntas:k

  1. A minha ideia de solução está no caminho certo?
  2. Como as novas variáveis ​​devem ser criadas para que possam ser usadas para representar a restrição de cardinalidade ?k
Aden Dong
fonte
5
Apenas uma observação: seu problema é conhecido como HITTING SET , que é uma formulação equivalente do problema SET COVER .
precisa saber é o seguinte

Respostas:

13

Parece que você está tentando calcular um hipergrafo transversal do tamanho . Ou seja, é seu hipergrafo e é sua transversal. Uma tradução padrão é expressar as cláusulas como você possui e depois converter a restrição de comprimento em uma restrição de cardinalidade.k{T1,,Tm}S

Portanto, use sua codificação existente, ou seja, e adicione cláusulas que codificam .1jmiTjxi1inxik

1inxik é uma restrição de cardinalidade. Existem várias traduções diferentes de restrições de cardinalidade no SAT.

A conversão de restrição de cardinalidade mais simples, porém bastante grande, é apenas . Dessa forma, cada disjunção representa a restrição - para todos os subconjuntos de do tamanho k + 1. Ou seja, garantimos que não há como definir mais de k variáveis. Observe que esse não é o tamanho polinomial em ¬ i X X i X { 1 , ... , n } kX{1,,n},|X|=k+1iX¬xi¬iXxiX{1,,n}k

Alguns links para artigos sobre traduções de restrições de cardinalidade com maior eficiência de espaço e tamanho polinomial em k :

Se você está realmente interessado em resolver esses problemas, talvez seja melhor formulá-los como problemas pseudo-booleanos (consulte o artigo da wiki sobre problemas pseudo-booleanos ) e use solucionadores pseudo-booleanos (consulte competição pseudo-booleana ). Dessa forma, as restrições de cardinalidade são apenas restrições pseudo-booleanas e fazem parte da linguagem - espero que o solucionador pseudo-booleano as manipule diretamente e, portanto, com mais eficiência.

MGwynne
fonte
1
Descreva todos os links em breve (pelo menos, autor e título) para que as pessoas possam encontrar os documentos caso os links quebrem. Provavelmente é melhor usar o DOI, se disponível.
Raphael
1
@Raphael Bom ponto! Desculpas que eu deveria ter feito isso para começar. Eu atualizei todos os links; Não tenho certeza se a Springer fornece DOIs, mas deve haver informações suficientes agora para encontrá-los se os links quebrarem. Nota: Não vinculo aos PDFs oficiais da Springer para evitar problemas de acesso.
precisa saber é o seguinte
Mas parece que a redução que você deu não está no tempo polinomial, certo?
Aden Dong
@AdenDong Você não disse nada sobre polinômio;). A tradução simples de restrição de cardinalidade que mencionei não é polinomial em (mas é para k fixo ). As traduções das restrições de cardinalidade fornecidas nos artigos que listo são polinomiais em k - usando novas variáveis. Atualizei minha resposta para deixar isso mais claro. kkk
precisa saber é o seguinte
MGwynne, costumo sempre vincular o DOI oficial, mesmo se for pago, a fim de ser à prova de futuro e versões gratuitas adicionalmente. Mas como é agora, qualquer um deve encontrar os papéis, então está tudo bem.
Raphael
6

k

Γ2,1+Γ2,1+

Suponho que você esteja procurando uma redução explícita, mas, se não, pode sempre voltar ao Teorema de Cook-Levin .

Luke Mathieson
fonte