Zmniejsz następujący problem do SAT

21

Oto problem. Biorąc pod uwagę , gdzie każdy T i{ 1 , , n } . Czy istnieje podzbiór S { 1 , , n } o rozmiarze co najwyżej k taki, że S T i dla wszystkich ja ? Próbuję zredukować ten problem do SAT. Moim pomysłem na rozwiązanie byłoby posiadanie zmiennej x ik,n,T1,,TmTi{1,,n}S{1,,n}kSTiixidla każdego z 1 do . Dla każdego T i utwórz klauzulę ( x i 1x i k ), jeśli T i = { i 1 , , i k } . Następnie i wszystkie te klauzule razem. Ale to wyraźnie nie jest kompletne rozwiązanie, ponieważ nie reprezentuje ograniczenia, które S musi mieć co najwyżej k elementów. Wiem, że muszę tworzyć więcej zmiennych, ale po prostu nie jestem pewien, jak to zrobić. Mam więc dwa pytania:nTi(xi1xik)Ti={i1,,ik}Sk

  1. Czy mój pomysł na rozwiązanie jest właściwy?
  2. Jak należy utworzyć nowe zmienne, aby można je było wykorzystać do przedstawienia ograniczenia liczności ?k
Aden Dong
źródło
5
Tylko uwaga: Twój problem jest znany jako HITTING SET , który jest równoważnym sformułowaniem problemu SET COVER .
A.Schulz,

Odpowiedzi:

13

Wygląda na to, że próbujesz obliczyć przekrój poprzeczny wielkości . Oznacza to, że { T 1 , , T m } jest twoim hipergrrafem, a S jest twoim poprzecznym. Tłumaczenie standardowe polega na wyrażeniu istniejących klauzul, a następnie przetłumaczeniu ograniczenia długości na ograniczenie liczności.k{T1,,Tm}S

1jmiTjxi1inxik

1inxik

X{1,,n},|X|=k+1iX¬xi¬iXxiX{1,,n}k

k

Jeśli faktycznie jesteś zainteresowany rozwiązaniem takich problemów, być może lepiej sformułować je jako problemy pseudo-boolowskie (zobacz artykuł wiki na temat problemów pseudo-boolean ) i użyć solverów pseudo-boolean (patrz konkurencja pseudo-boolean ). W ten sposób ograniczenia liczności są tylko ograniczeniami pseudo-boolowskimi i są częścią języka - miejmy nadzieję, że solver pseudo-boolowski obsługuje je bezpośrednio, a zatem bardziej wydajnie.

MGwynne
źródło
1
Opisz krótko wszystkie linki (przynajmniej autora i tytuł), aby ludzie mogli znaleźć dokumenty w przypadku zerwania linków. Prawdopodobnie najlepiej użyć DOI, jeśli jest dostępny.
Raphael
1
@Raphael Dobra uwaga! Przepraszam, że powinienem był to zrobić na początek. Zaktualizowałem teraz wszystkie linki; Nie jestem pewien, czy Springer zapewnia DOI, ale powinno być teraz wystarczająco dużo informacji, aby je znaleźć, jeśli linki się zepsują. Uwaga: nie linkuję do oficjalnych plików PDF firmy Springer, aby uniknąć problemów z dostępem.
MGwynne,
Wygląda jednak na to, że obniżka, której dokonałeś, nie jest wielomianowa, prawda?
Aden Dong
kkk
MGwynne, zwykle łączę oficjalny DOI, nawet jeśli jest on zaporowy, aby był przyszłościowy, a dodatkowo wersje darmowe. Ale tak jak teraz, każdy powinien znaleźć papiery, więc wszystko jest w porządku.
Raphael
6

k

Γ2,1+Γ2,1+

Zakładam, że szukasz wyraźnej redukcji, ale jeśli nie, zawsze możesz po prostu wrócić do twierdzenia Cooka-Levina .

Luke Mathieson
źródło