Czy Dominosa NP-Hard?

Dominosa to stosunkowo nowa gra logiczna. Jest odtwarzany na siatce . Przed rozpoczęciem gry kości domina są umieszczane na siatce (tworząc idealne kafelki ). W następnym kroku kości domina są ukryte, pozostawiając tylko liczby ujawnione. Celem gry jest odzyskanie pierwotnego ułożenia kości domina. Możesz zagrać w tę grę tutaj: http://www.puzzle-dominosa.com/ : $(n+1)\times(n+2)$ $\left(0,0\right),\left(0,1\right),\ldots,\left(n,n\right)$

Zasady:

Zasady są proste. Musisz znaleźć lokalizację wszystkich domino na siatce. Domino to para liczb. Możesz mieć tylko jedną z każdej pary.

Mam kilka algorytmów wielomianowych, które rozwiązują stosunkowo niewielką część układanki. Mogę również wykazać, że typowe siatki Dominosa mają co najmniej rozwiązania. $2^{\frac{n}{2}+o\left(n\right)}$

Czy Dominosa NP-Hard?

— Yoav bar sinai
źródło

„Zagadkę można łatwo sprowadzić do problemu SAT lub ILP”. Aby udowodnić kompletność NP, nie chciałbyś być na odwrót?

— Dennis Meng

@DennisMeng Celem redukcji wymienionych w pytaniu jest ustalenie, że problem dotyczy NP. Pozostaje tylko udowodnić, że jest to trudne NP. Nawiasem mówiąc, nie trzeba zmniejszać, aby zobaczyć, że problem dotyczy NP. Układ domina sam w sobie jest wielomianowym świadectwem rozwiązalności.

Zakładam, że problem, którego dotyczy kompletność NP, polega na tym, że biorąc pod uwagę układ liczb, wynika on z układu domina. Jeśli problemem jest faktyczne ułożenie domino (gdy istnieje), to problem nie jest problemem decyzyjnym i „NP zakończone” nie ma sensu.

@AndreasBlass Można również rozważyć większy problem: Biorąc pod uwagę podzbiory elementów Domina od do oraz wykres z wierzchołkami oznaczonymi od do , określ, czy możliwe jest pokrycie go danymi domenami. Jeśli ten problem występuje w P, to istnieje algorytm czasu P, aby odzyskać oryginalne kafelkowanie, ponieważ możesz spróbować usunąć krawędź i przetestować w czasie P, czy możliwe jest wypełnienie siatki.

k

$k$

1

$1$

n

$n$

G

$G$

2 k

$2k$

1

$1$

n

$n$

Według artykułu G. Nordha o nazwie NP-zupełność uogólnionych sekwencji wielu Skolemów, następujący podobny problem jest NP-zupełny. Instancja: Wykres , podział krawędzi na zestawy rozłączne: z tak, że żadne dwie krawędzie o tej samej etykiecie nie dzielą wierzchołka. PYTANIE: Czy istnieje podzbiór z taki, że żadne dwie krawędzie w M nie mają wspólnego wierzchołka i taki, że M zawiera co najwyżej jedną krawędź z każdego ?

G = (V, E)

$G=(V,E)$

E_{1}, E_{2}, . . ., E_{m}, | m | \geq | V | / 2

$E_{1},E_{2},...,E_{m}, |m|\ge|V|/2$

| E_{i} | \leq 2, i = 1, \dots, m

$|E_{i}|\le2,\ i=1,\ldots,m$

M \subset E

$M\subset E$

| M | = | V | / 2

$|M|=|V|/2$

E_{i}, i = 1, \dots, m

$E_{i},\ i=1,\ldots,m$

— Yoav bar sinai

Odpowiedzi:

Uwaga: Jest to kontynuacja i poprawka mojej innej odpowiedzi .

Problemy z redukcją

Przypomnij sobie problem decyzyjny:

Czy istnieje idealne kafelkowanie pokrywające daną siatkę unikalnymi płytkami? $(n+1) \times (n+2)$ $n$

Tak więc dla siatki możemy użyć tylko zmiennych. $(n+1) \times (n+2)$ $n$

Ale:

Nasza redukcja wymaga wielu unikalnych zmiennych, znacznie więcej niż . $\mathcal O(n)$

Ponadto nasze przewody są otwarte, co prowadzi do:

Skąd wiemy, że możemy kafelkować otwarte obszary?

Aby rozwiązać pierwszy problem, sztucznie powiększamy planszę; Zasadniczo tworzymy równą liczbie zmiennych, których faktycznie potrzebujemy, a następnie tworzymy siatkę wielkości i umieszczamy naszą siatkę w lewym dolnym rogu. Doprowadzi to do kwadratowego wybuchu. $n$ $(n+1)\times(n+2)$

W przypadku drugiego problemu musimy nieco przemyśleć nasze gadżety.

Może to wydawać się nieco zniechęcające, aby udowodnić, że możemy z powodzeniem ułożyć resztę planszy zgodnie z regułą. Zaczynamy więc od tej samej strategii, której użyłbyś do wygenerowania plansz wielkości : $(n+1)\times(n+2)$

Najpierw generujemy zestaw wszystkich możliwych płytek. Wszystkie te płytki będą musiały zostać umieszczone na planszy. Następnie usuwamy płytki i pozostawiamy ich kwadraty.

Jednak nasze gadżety nie gwarantują umieszczenia określonego zestawu płytek; umieszczone płytki zależą od stanu. Musimy więc ostrożnie modyfikować gadżety, aby zagwarantować, że poszczególne kafelki zostaną usunięte, bez względu na wybrany stan.

Zobaczmy więc nasze gadżety.

Drut i bramka-klauzula są problematyczne z dwóch powodów.

Nie wiemy, czy kwadraty otaczające drut lub bramę klauzulową można poprawnie kafelkować; w końcu niektóre druty można przesunąć w lewo, inne w prawo, a kafelkowanie pozostałych białych pól staje się trywialne. Będziemy odnosić się do tego problemu jako do problemu „przepływu”.
Nie ma możliwości dowiedzenia się, które kafelki usunąć z zestawu kafelków; w jednym stanie, jeden zestaw kwadratów, w drucie lub bramie klauzulowej, zostanie wyłożony kafelkami, w innym stanie, będzie wyłożony zupełnie inny zestaw kwadratów.

Aby rozwiązać te problemy:

Najpierw generujemy zestaw wszystkich możliwych kafelków. Wszystkie te płytki będą musiały zostać umieszczone na planszy; umieszczając je na planszy, usuwamy płytkę z zestawu. Chociaż na początku możemy nie wiedzieć , ponieważ musimy jeszcze w pełni opisać formułę, możemy dodać wszystkie nowe możliwości płytek, zwiększając , w razie potrzeby. Wszystkie płytki, które usuwamy z tego zestawu, muszą gwarantować możliwość umieszczenia (przynajmniej, aby można je było umieścić, jeśli formuła jest zadowalająca). Wzywamy do usunięcia płytki z zestawu płytek, aby „rozładować” płytkę z zestawu płytek, tak jak w celu wywiązania się z naszego obowiązku umieszczenia jej na planszy. $n$ $n$
Musimy ostrożnie zaprojektować gadżety, aby zagwarantować, że poszczególne kafelki zostaną usunięte, bez względu na wybrany stan.
Musimy zamknąć nasze gadżety, aby nie pchały płytek wokół planszy, w zależności od ich stanu; raczej wszystkie ich państwa muszą zajmować tylko określony, dobrze określony obszar.
- Alternatywnie, należy zagwarantować , że wszystkie ich państwa będą w stanie zająć dobrze określony obszar; gwarantuje to zadowalające układanie płytek, ale nie gwarantuje, że wystąpią określone kafelki. W ten sam sposób powstaje gra Dominosa:
  - Najpierw płytki są generowane w zestawie;
  - Następnie płytki są układane w losowej konfiguracji,
  - Po umieszczeniu każdego kafelka jest on usuwany z zestawu kafelków.
  - Następnie płytki są usuwane z planszy, pozostawiając za sobą kwadraty.
  - Nie gwarantuje to, że zostanie wybrana zamierzona konfiguracja ,
  - Raczej to gwarancję, że przeznaczony konfiguracja może być wybrany, a więc istnieje rozwiązanie. Możemy zrobić to samo tutaj.
Po umieszczeniu wszystkich gadżetów formuły, zamiast domyślnego umieszczania unikalnych kwadratów, tj. Na całej „białej spacji”, upewniamy się, że biała przestrzeń to prostokątny obszar o jednym parzystym wymiarze, lub rozbicie białe na prostokąty o jednym parzystym wymiarze , i po prostu układamy białe pola pozostałymi kafelkami w zestawie kafelków. ${\star}$
Po umieszczeniu wszystkich płytek z zestawu wiemy, że wszystko można układać.
- Niektóre kafelki można oczywiście umieścić, na przykład te w ścianach, inne można umieścić tylko wtedy, gdy formuła jest zadowalająca, ze względu na charakter relacji między gadżetami.
Następnie usuwamy płytki i pozostawiamy ich kwadraty.

Zobaczmy więc nasze gadżety.

Wymuszanie gadżetu

Możemy wykonać dowolną liczbę elementów składowych, upewniając się, że nie można ich sparować ze sobą.

Powiedzmy na przykład, że chcemy wymusić , abyśmy mogli użyć jako elementu konstrukcyjnego. (zauważ, że jest dowolną zmienną, którą chcemy zmusić jako parę do siebie, niekoniecznie element konstrukcyjny, ponieważ wcześniej używaliśmy wartości ) $\mathbf{({1}{\star},{1}{\star})}$ $\mathbf{1}{\star}$ ${1}{\star}$ $1$

Aby zagwarantować, że nasze zastrzega -building blokowe , będziemy umieścić go na dolnej ścianie w następującej konfiguracji: będziemy umieszczać numer zastrzeżony, nazwijmy go ścianę niczym up-tack (w kształcie ); przy ścianie i jeden w drugim rzędzie pośrodku. Następnie kolejne dwa numery, nazwijmy je i ; są one unikalne dla tego gadżetu. je na lewym i prawym . $\mathbf {1}{\star}$ $\mathbf{({1}{\star},{1}{\star})}$ $\mathbf{1}{\star}$ $\bot$ $3$ ${\mathbf 2}{\star}$ ${\mathbf 3}{\star}$ $\mathbf{1}{\star}$

Zilustrowana poniżej wspólna czarna ramka jest dolną częścią planszy, opis od lewej do prawej.

Konfiguracja gadżetu. Każdy i tutaj są unikalne dla tego gadżetu. ${\mathbf 2}{\star}$ ${\mathbf 3}{\star}$
3 możliwe stany sąsiadującego środka . $\mathbf{1}{\star}$

wprowadź opis zdjęcia tutaj

Po wykonaniu tej czynności możemy zagwarantować, że nasz gadżet będzie można kafelkować za pomocą określonego zestawu płytek, jednocześnie gwarantując, że nasz gadżet musi wymusić parę . $\mathbf{({1}{\star},{1}{\star})}$

Wiemy, że muszą wystąpić , ponieważ wszystkie 3 możliwe stany kafelkowania dolnej środkowej , kafelek jako , jak pokazano na rysunku po prawej stronie powyżej. $\mathbf{({1}{\star},{1}{\star})}$ $\mathbf{1}{\star}$ $\mathbf{({1}{\star},{1}{\star})}$
Pozostałe kafelki można kafelkować jako i , zakrywając gadżet. W ten sposób możemy usunąć te płytki z naszego globalnego zestawu płytek. Zilustrowane poniżej. $({1}{\star},{2}{\star})$ $({1}{\star},{3}{\star})$

Opis, od lewej do prawej:

Lewy, górny: Lewy stan, Lewy, dolny: Prawidłowe kafelki pozostałych kwadratów.
Środek, góra: stan środkowy, środek, dół: prawidłowe kafelki pozostałych kwadratów.
Z prawej, u góry: Stan z prawej, Z prawej, u dołu: Prawidłowe zestawienie pozostałych kwadratów.

wprowadź opis zdjęcia tutaj

Pamiętaj, że kafelki pozostałych kwadratów nie są wymuszone , ponieważ mogą kafelkować sąsiadów w pobliżu zamiast , ale ponieważ jest to prawidłowe kafelkowanie planszy we wszystkich stanach, możemy je usunąć z zestaw kafelków i załóżmy, że zostaną ułożone w taki sam sposób. Ponieważ wiemy, że możliwe jest prawidłowe kafelkowanie, mamy co najmniej jeden możliwy kafelek planszy, jeśli formuła jest zadowalająca. Chociaż nie ma żadnej gwarancji, że zostaną one ułożone w ten sposób, istnieje gwarancja, że zostanie wymuszona. $\mathbf{1}{\star}$ $\mathbf{({1}{\star},{1}{\star})}$

Uwaga: jeśli nie jesteś z tego zadowolony lub jesteś zdezorientowany różnicą między „zdolnością do układania płytek” a „zmuszaniem do układania płytek”, możesz po prostu umieścić ścianę wokół gadżetu , tak samo jak my zrób ścianę poniżej dla gadżetu klauzulowego. $3\times 2$ $3\times 2$

Ten gadżet nie jest zamknięty, ponieważ nie musi być (ale możesz, jeśli chcesz). Nie musi tak być, ponieważ ma wykonalną konfigurację, którą możemy usunąć z zestawu kafelków. Chociaż może być możliwe wykonanie innej konfiguracji, nie wpływa to na satysfakcję problemu.

Następujące płytki są gwarantowane do kafelkowania (dzięki czemu można je usunąć z zestawu płytek): $\mathbf{({1}{\star},{1}{\star})}$

Poniżej płytki gwarancją mogą być wyłożone (a zatem mogą być usuwane z płytek-zestaw) $({1}{\star},{2}{\star}), ({1}{\star},{3}{\star})$

Jeśli zdecydujesz się zamknąć ten gadżet ścianą, wówczas również będzie objęty gwarancją. $({1}{\star},{2}{\star}), ({1}{\star},{3}{\star})$

Nowe bramy drutowe i klauzulowe

Ze względu na problemy z przepływem i opróżnianiem zestawu płytek musimy nieco przeprojektować drut.

Jednym ze sposobów rozwiązania problemu z przepływem jest uczynienie z drutu obwodu, a nie tylko prostych stanów z lewej strony; oznacza to, że byłby okrągły zamiast linii, a zatem jeśli górna część koła zostanie przesunięta w prawo, spód zostanie przesunięty w lewo. To rozwiązuje problem z przepływem.

Idąc tą drogą, możemy zmienić drut i bramkę, aby rozwiązać oba problemy.

Zastrzeganie i $\mathcal T$ $\mathcal F$

Pozwól nam przedstawić dwa nowe uniwersalne wartości, i . Te dwie wartości są uniwersalne; rzeczywiste wartości w siatce, takie jak wartości kwadratowe i (ponieważ zgodnie z umową zarezerwowaliśmy jako element konstrukcyjny ścian) lub cokolwiek innego. Reprezentują odpowiednio prawdę i fałsz. $\mathcal T$ $\mathcal F$ $2$ $3$ $1$

Wymuszamy rezerwację płytek , , w następujący sposób; ilustracja poniżej, opis od lewej do prawej: $(\mathcal T, \mathcal F)$ $(\mathcal T, \mathcal T)$ $(\mathcal F, \mathcal F)$

Używamy tego samego schematu, jak wymuszanie dowolnego , używając jako . Każdy i tutaj są unikalne dla tego gadżetu. $\mathbf{({1}{\star},{1}{\star})}$ $\mathcal T$ $\mathbf{1}{\star}$ ${\mathbf 2}{\star}$ ${\mathbf 3}{\star}$
Używamy tego samego schematu, jak wymuszanie dowolnego , używając jako Każde i są tutaj unikalne dla tego gadżetu. $\mathbf{({1}{\star},{1}{\star})}$ $\mathcal F$ $\mathbf{1}{\star}$ ${\mathbf 2}{\star}$ ${\mathbf 3}{\star}$
Korzystamy z tego samego schematu, co wymuszanie płytki , używając jako na środku i w innych miejscach podwyższenia. To zmusza do układania płytek. i mogą kafelki za pomocą , więc usuwamy je z zestawu kafelków. Każdy i tutaj są unikalne dla tego gadżetu. $\mathbf{({1}{\star},{1}{\star})}$ $\mathcal F$ $\mathbf{1}{\star}$ $\mathcal T$ $(\mathcal F, \mathcal T)$ ${\mathbf 2}{\star}$ ${\mathbf 3}{\star}$ $\mathcal T$ ${\mathbf 2}{\star}$ ${\mathbf 3}{\star}$

wprowadź opis zdjęcia tutaj

Drut

Każdy drut zaczyna się i kończy wartością, nazwijmy go , który jest unikalny dla drutu. Dla każdej klauzuli, w której uczestniczy drut, drut będzie miał dwie wartości drutu, i , które są unikalne dla każdego drutu i uczestniczą w tej samej klauzuli. Ilustracja poniżej z opisem od lewej do prawej. ${A}{\star}$ ${x}{\star}$ ${x'}{\star}$

Drut, który uczestniczy w jednej klauzuli. Drut ma wysokość i ma długość , gdzie jest liczbą klauzul, w których uczestniczy drut. Drut jest wypełniony dwoma po lewej stronie i dwoma po prawej stronie. Jest on oczywiście otoczony ze wszystkich stron ścianą, oznaczoną niebieskim konturem. Zauważ, że jest unikalny dla tego drutu i będzie używany tylko w tym drucie oraz w klauzuli, w której uczestniczy. $2$ $2*p+3$ $p$ ${A}{\star}$ ${1}{\star}$

wprowadź opis zdjęcia tutaj

Poniżej pokazano dwa stany, opisy od lewej do prawej.

Drut, który uczestniczy w jednej klauzuli, w stanie prawdziwym. Drut uważa się za prawdziwy, gdy kwadraty są sparowane z kwadratami , a kwadraty są sparowane z kwadratami Jest uważane za fałszywe w innym stanie, w którym kafelkowanie jest odwrócone. Uwaga jak Dachówka jest zmuszony raz płytki wybrano: są już zmuszeni wcześniej, więc reszta płytki musi być pozioma. ${x}{\star}$ $\mathcal T$ ${x'}{\star}$ $\mathcal F$ ${A}{\star}$ $(\mathcal T,\mathcal F)$
Ten sam drut w stanie fałszywym.

wprowadź opis zdjęcia tutaj

Gdy uczestniczysz w większej liczbie klauzul, istnieje większa wartość i , jedna para dla każdej klauzuli, w której uczestniczy drut. Naprzemiennie znajdują się na górze i na dole, podobnie jak kwadraty i które oddzielają każdy para. ${x}{\star}$ ${x'}{\star}$ $\mathcal T$ $\mathcal F$ ${x}{\star}, {x'}{\star}$

wprowadź opis zdjęcia tutaj

Dwa odpowiadające stany.

wprowadź opis zdjęcia tutaj

Ten gadżet jest zamknięty , więc nie ma „problemu z przepływem”.

Zauważ, że w obu stanach zbieramy następujące kafelki, bez względu na stan: , , . $({A}{\star},{A}{\star})$ $({A}{\star},\mathcal T)$ $({A}{\star},\mathcal F)$

Istnieją jednak pewne kafelki, których nie jesteśmy pewni; w jednym stanie możemy usunąć z zestawu kafelków, podczas gdy w innym stanie możemy usunąć $({1}{\star}, \mathcal T), ({1'}{\star},\mathcal F), ({2}{\star},\mathcal T), ({2'}{\star},\mathcal F) ...$ z zestawu kafelków, więc które kafelki rzeczywiście możemy usunąć? Odpowiedź brzmi: brama klauzuli ma ten sam problem, ale z przeciwległym zestawem płytek. Zawsze będzie zbierać pozostałe, przeciwne i niepobrane płytki, jak zobaczymy w następnej sekcji. Ponieważ każde z nich jest połączone z bramką klauzuli, będziemy mogli usunąć je obie. $({1}{\star}, \mathcal F), ({1'}{\star},\mathcal T), ({2}{\star},\mathcal F), ({2'}{\star},\mathcal T) ...$

Klauzula

Następnie stworzymy pierwszą iterację nowej bramki klauzuli. Składa się z gadżetu , otoczonego ścianami. Wewnątrz gadżetu umieszczamy jedną w górnej środkowej części i dwa kwadraty w dolnych rogach; jeden w lewym dolnym rogu i jeden w prawym dolnym rogu. Pozostałe kwadraty będą wartościami reprezentującymi zmienne drutowe trzech różnych drutów. Nazwijmy te i . zostanie zmuszone do parowania się z jednym z przewodów-zmiennych, pozostałe zmienne z drutu będzie parować z wartości. Ilustracje poniżej, opisy od lewej do prawej. $2\times 3$ $\mathcal F$ $\mathcal T$ ${a}{\star}, {b}{\star},$ ${c}{\star}$ $\mathcal F$ $\mathcal T$

Po lewej: konfiguracja dla pierwszej iteracji nowej klauzuli-klauzuli.
Prawo Trzy możliwe stany płytki $\mathcal F$

wprowadź opis zdjęcia tutaj

Te trzy stany prowadzą do trzech możliwych przechyleń. Ilustracja poniżej, opisy od lewej do prawej.

Lewy, górny : kafelkowy lewy, lewy, dolny: Kafelkowy pozostałe kwadraty. $\mathcal F$
Środkowy, górny : kafelkowy prawy, Środkowy, dolny: Kafelkowy pozostałe kwadraty. $\mathcal F$
Prawo, góra : sąsiadująco, prawo, dół: sąsiadujące kwadraty. $\mathcal F$

wprowadź opis zdjęcia tutaj

Ponieważ zostanie sparowany z jedną ze zmiennych drutowych w klauzuli , tej zmiennej drutowej nie można już sparować z zmienną w przewodzie ; w ten sposób zmuszając drut do prawdziwości. I odwrotnie, pozostałe zmienne drutowe, które sąsiadują z będą zmuszone do wstawiania z przewodami. Jest to dokładnie te same ograniczenia jak punktu. $\mathcal F$ $\mathcal F$ $\mathcal T$ $\mathcal F$ $\rm 1\text{-in-}3\text{-}S{\small AT}$

Uwaga, i są z drutu są zmienne, ale mogą odnosić się do każdego lub drutu zmiennej; użycie zasadniczo neguje zmienną drutową. ${a}{\star}, {b}{\star},$ ${c}{\star}$ ${x}{\star}$ ${x'}{\star}$ ${x'}{\star}$

Jeden dodatek: aby wywiązać się z obowiązku wiedzieć, które płytki można usunąć z zestawu płytek, musimy „podwoić i przeciwstawić” klauzulę. Co mam na myśli to, jest, aby kolejne gadżet, z dodatkowych zmiennych reprezentujących negacji oraz . Nazwijmy te i . Te muszą być zanegowane wartości zmiennej druciane $3\times 2$ $3$ ${a}{\star}, {b}{\star},$ ${c}{\star}$ ${a'}{\star}, {b'}{\star},$ ${c'}{\star}$ I . Tengadżet jest inny, ponieważ będzie miał w środku i dwiewartości w rogach; dokładnie przeciwnie do opisanego dotychczas gadżetu klauzulowego. Poprzez „podwojenie” takiej klauzuli ponownie dodajemy te same ograniczenia, co gadżet opisany powyżej. Jednak rozładowujemy również wszystkie kombinacje ${a}{\star}, {b}{\star},$ ${c}{\star}$ $3\times 2$ $\mathcal T$ $\mathcal F$ z płytek-zestawu, dla każdej zmiennej (a zatemi , a także, ponieważ są one przecież, drut-zmienne). Zilustrowane poniżej opisy od lewej do prawej. $(\mathcal T, {x}{\star}), (\mathcal T, {x'}{\star}), (\mathcal F, {x}{\star}), (\mathcal F, {x'}{\star})$ ${a}{\star}, {b}{\star},$ ${c}{\star}$

Klauzula „podwójnego i antykoncepcyjnego”. Dolna sekcja to klauzula opisana powyżej; górna sekcja to nowo opisana klauzula antykoncepcyjna. Nowa klauzula ma dokładnie takie same ograniczenia logiczne; jest to przeciwieństwo dolnej klauzuli. Łącznie te połączone gadżety i drut rozładowują wszystkie kombinacje z zestawu płytek, dla każda zmienna przewodowa uczestnicząca w klauzuli. $(\mathcal T, {x}{\star}), (\mathcal F, {x}{\star}), (\mathcal T, {x'}{\star}), (\mathcal F, {x'}{\star})$
Niebieska linia pośrodku lewej skrajnej figury ułatwia przeglądanie; w rzeczywistości można go usunąć bez zezwolenia na kolejne stany.

wprowadź opis zdjęcia tutaj

Weźmy więc przykład, aby pokazać, że wszystkie płytki są rozładowywane zgodnie z obietnicą. Zilustrowane poniżej, opis od lewej do prawej.

Figura drutu uczestniczącego w jednej klauzuli; dla klauzuli wybrano stan. Tutaj używamy , podczas gdy i reprezentują inne wartości drutów w tym punkcie. ${1}{\star}={b}{\star}$ ${a}{\star}$ ${b}{\star}$
Dla danego państwa w klauzuli, w wartość jest zmuszona być połączony z sąsiednim . ${1}{\star}$ $\mathcal T$
Powoduje to, że drut jest zmuszony do prawdziwej wartości (można powiedzieć, gdy dodatnia zmienna drutu jest zmuszona do sparowania z , a ujemna zmienna jest zmuszona do sparowania z , jak wyjaśniono powyżej). $\mathcal T$ $\mathcal F$
Wymusza to w klauzuli antykoncepcyjnej (górna część klauzuli) z w klauzuli. Teraz, gdy spojrzysz na drut, każda płytka w przewodzie jest z pewnością rozładowana: albo rozładowana w samym przewodzie, albo w odpowiednim gadżecie klauzuli. W tym stanie mamy kafelki, , , , , ${1'}{\star}$ $\mathcal T$ $({A}{\star},{A}{\star})$ $({A}{\star},\mathcal T)$ $({A}{\star},\mathcal F)$ $({1}{\star},\mathcal T)$ , i . $({1}{\star},\mathcal F)$ $({1'}{\star},\mathcal F)$ $({1'}{\star},\mathcal T)$

wprowadź opis zdjęcia tutaj

Próbując w innym stanie, otrzymujemy ilustrację poniżej, opis od lewej do prawej.

Klauzula jest w innym stanie, kafelkowanie na jeden z dwóch sposobów. $({1}{\star},\mathcal T$
Dlatego jest wymuszone na drucie, $({1}{\star},\mathcal F$
Prowadząc resztę drutu do płytki odpowiednio, i oceniaj drut jako fałszywy.
Wreszcie, w przeciwstawnym / górnym odcinku gadżetu klauzulowego musi , ponieważ jest brane do drutu. W tym stanie mamy kafelki, , , , , $({1'}{\star},\mathcal F)$ $({1'}{\star},\mathcal T)$ $({A}{\star},{A}{\star})$ $({A}{\star},\mathcal T)$ $({A}{\star},\mathcal F)$ $({1}{\star},\mathcal T)$ , i . Są to te same płytki, które zostały rozładowane jak w drugim stanie. $({1}{\star},\mathcal F)$ $({1'}{\star},\mathcal F)$ $({1'}{\star},\mathcal T)$

wprowadź opis zdjęcia tutaj

Dlatego w obu stanach rozładowujemy te same płytki. Dlatego drut i klauzula razem z powodzeniem rozładowują określone płytki, jeśli jest zadowalające przypisanie.

Ten gadżet jest zamknięty , więc nie będzie problemu z przepływem. Klauzula-gadżet wraz z gadżetem drucianym gwarantują zawsze rozładowywanie tych samych wartości pary kafelków , a zatem możemy je rozładować, nawet jeśli nie wiemy, w jaki sposób będą kafelki.

Teraz wszystkie nasze gadżety spełniają kryteria.

Sformułowanie

W naszym ostatecznym sformułowaniu tworzymy trzy rzędy gadżetów, każdy oddzielony poziomą ścianą.

Na dole umieszczamy gadżety do wymuszania, które mają dwa kafelki wysokości. Musimy zmuszając gadżet dla bloku budowlanego, a dla połączeń i . Umieszczamy wymuszone gadżety bezpośrednio obok siebie. $\mathcal T$ $\mathcal F$
W środkowym rzędzie umieszczamy druciane gadżety, poziomo, które mają dwie płytki wysokości. Druciane gadżety powinny być oddzielone od siebie pionową ścianą.
W górnym rzędzie umieszczamy gadżety klauzulowe, które mają cztery płytki wysokości. Gadżety klauzulowe powinny być oddzielone od siebie pionową ścianą.

Poniższe ilustracje, opisy nad każdą figurą. Kliknij obrazy, aby uzyskać pełną rozdzielczość. Kod źródłowy do reprodukcji / generowania obrazów znajduje się na dole strony.

Używając wzoru jako przykład, mamy satysfakcjonujące rozwiązanie $\Phi(\mathbf x)= (x_1,\neg x_2, x_3) \wedge (x_2,\neg x_3,x_4) \wedge (x_1,x_2,\neg x_4)$ $(\neg x_1,x_2,x_3,\neg x_4)$ jako świadek.

Najpierw zaczynamy od poziomych ścian oddzielających rzędy gadżetów. Pokazujemy kwadraty i pary, które są zmuszone do układania płytek w ścianach.

Następnie pokazujemy gadżety. Niebieski kontur reprezentuje granice gadżetów; niebieski przerywany dla gadżetów forsowania, ponieważ nie będą otoczone ścianami. Uwaga: linia pośrodku gadżetu klauzuli nie jest otoczona ścianą; ma na celu ułatwienie oglądania; usunięcie linii nie pozwala na pojawienie się więcej stanów w klauzuli, jak wyjaśniono powyżej, ale pokazujemy niebieską linię dla tej demonstracji. Uwaga: używamy nazw kwadratowych, aby nadać liczbom czytelność semantyczną, jeśli ma to zastosowanie. Każda nazwa reprezentuje wartość liczbową.

Tutaj wypełniamy pionowe ściany.

Tutaj wypełniamy rozwiązanie dla świadka; tzn. jest to rozwiązanie kafelkowe, jeśli używasz rozwiązania SAT do jego wygenerowania.

$n$

Tutaj wypełniamy pozostałe kwadraty trywialnym prawidłowym kafelkiem.

Tutaj pokazujemy prawy dolny róg siatki.

Tutaj pokazujemy prawy górny róg siatki. Zwróć uwagę, że pionowe płytki nie pasują już; więc w razie potrzeby układamy górny rząd poziomo.

I wreszcie lewy górny róg.

Generowanie całej planszy naraz przez TeX kończy się niepowodzeniem z błędami braku pamięci z pdflatex, więc jeśli chcesz to zobaczyć, musisz wygenerować klipy i połączyć je razem. Koniecznie sprawdź przeglądarkę notebooków .

Źródła TikZ

Generator gier:

graphtex.py

Konwertuje TeX na svg, używając pdflatex, pdfcairo (poppler) i rsvg-convert (libsvg)
dominosa.py

Zawiera logikę konwersji, weryfikację rozwiązania gry i logikę rysowania
dominosa_demo.py

Wykonalne demo, które generuje obrazy użyte w powyższej odpowiedzi. Zrzuca obrazy do bieżącego katalogu roboczego.
dominosa_demo.ipynb

Demo ipython, które generuje obrazy użyte w powyższej odpowiedzi.
- Zobacz przeglądarkę notesów, aby zobaczyć wyniki

— Realz Slaw
źródło

Jest to bardzo widowiskowe, dziękuję bardzo ..

— Yoav bar sinai

Poinformuj mnie, że masz wersję arXiv. To może być bardziej uzasadnione dla tej platformy zawierać wstępny szkic i link do pełnej papieru.

— Raphael

${\rm D{\small OMINOSA}}$

Granie w grę jest problemem optymalizacji; znalezienie prawidłowego kafelka domina, tak aby obejmował wszystkie kwadraty. Wersja decyzyjna tego problemu to:

$(n+1) \times (n+2)$ $n$

Oczywiście problem optymalizacji, problem znalezienia rozwiązania gry jest co najmniej tak samo trudny lub trudniejszy niż problem decyzyjny.

$1\text{-}3\text{-in-}{\rm S{\small AT}}$

${\rm P=NP}$ ${\rm D {\small OMINOSA}}$

$1\text{-}3\text{-in-}{\rm S{\small AT}}$ ${\rm D {\small OMINOSA}}$

Wprowadzenie

$3\text{-}{\rm S{\small AT}}$ ${\rm C{\small IRCUIT}S{\small AT}}$

${\rm C{\small IRCUIT}S{\small AT}}$ ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$

$3\text{-}{\rm S{\small AT}}$ ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$ $3\text{-}{\rm S{\small AT}}$ ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$

${\rm P{\small LANAR}}\text{-}3\text{-}{\rm S{\small AT}}$ ${\rm P{\small LANAR}\text{-}C{\small IRCUIT}S{\small AT}}$

$3\text{-}{\rm S{\small AT}}$

$1\text{-in-}3\text{-}{\rm S{\small AT}}$ $1\text{-in-}3$ $3\text{-}{\rm S{\small AT}}$

${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$

${\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$ ${\rm P{\small LANAR}}\text{-}{\rm M{\small ONOTONE}}\text{-}1\text{-in-}3\text{-}{\rm S{\small AT}}$ ${\rm C{\small IRCUIT}S{\small AT}}$

\begin{array}{cccccc} P R O B L E M & M O N O T O N E & P L A N A R & 1 -in- 3 & N P - h a r d \\ 3 - S A T & No & No & No & Yes \\ M O N O T O N E - 3 - S A T & Yes & No & No & {No}^{1} \\ P L A N A R - 3 - S A T & No & Yes & No & {Yes}^{2} \\ 1 -in- 3 - S A T & No & No & Yes & {Yes}^{3} \\ \binom{P L A N A R}{1 -in- 3 - S A T} & No & Yes & Yes & {Yes}^{4} \\ \binom{M O N O T O N E -}{1 -in- 3 - S A T} & Yes & No & Yes & {Yes}^{5} \\ \binom{P L A N A R -}{M O N O T O N E - 3 - S A T} & Yes & Yes & No & {Yes!}^{6} \\ \binom{P L A N A R - M O N O T O N E -}{1 -in- 3 - S A T} & Yes & Yes & Yes & {Yes}^{7} \end{array}

$\begin{array}{c|c|c|ccc} &&&&\hspace{1em}&\hline\\ {\rm\mathbf{P{\small ROBLEM}}} &\scriptsize{{\rm\mathbf{MONOTONE}}} &\scriptsize{{\rm\mathbf{PLANAR}}} &\scriptsize{{\rm\mathbf{1\text{-in-}3}}} &&{\rm\mathbf{NP\text{-}hard}} \\ \hline\\ {\rm\mathbf{3\text{-} S{\small AT}}} & \text{No} & \text{No} & \text{No} && \text{Yes}\\ \hline\\ {\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}} & \text{Yes} & \text{No} & \text{No} && {\text{No}}^1\\ {\rm\mathbf{P{\small LANAR}\text{-}3\text{-} S{\small AT}}} & \text{No} & \text{Yes} & \text{No} && {\text{Yes}}^2\\ {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}} & \text{No} & \text{No} & \text{Yes} && {\text{Yes}}^3\\ \hline\\ \genfrac{}{}{0}{1} {\rm\mathbf{P{\small LANAR}}} {\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}} & \text{No} & \text{Yes} & \text{Yes} && {\text{Yes}}^4\\\\ \genfrac{}{}{0}{1} {{\rm\mathbf{M{\small ONOTONE}\text{-} }}} {{\rm\mathbf{1\text{-in-}3\text{-} S{\small AT}}}} & \text{Yes} & \text{No} & \text{Yes} && {\text{Yes}}^5\\\\ \genfrac{}{}{0}{1} {{\rm\mathbf{P{\small LANAR}\text{-}}}} {{\rm\mathbf{M{\small ONOTONE}\text{-}3\text{-} S{\small AT}}}} & \text{Yes} & \text{Yes} & \text{No} && {\text{Yes!}}^6\\ \hline\\ \genfrac{}{}{0}{1} {{\rm\mathbf{P{\small LANAR}\text{-}M{\small ONOTONE}\text{-} }}} {{\rm\mathbf{1\text{-in-}3\text{-}S{\small AT}}}} & \text{Yes} & \text{Yes} & \text{Yes} && {\text{Yes}}^7\\ \end{array}$

$3\text{-}{\rm S{\small AT}}$

Co to jest „gadżet”? Gadżet to pewna konstrukcja problemu, która jest pomocna jako element konstrukcyjny do budowania bram / przewodów / klauzul. Niektóre gadżety będą miały ograniczony zestaw stanów; na przykład gadżet z dwoma stanami może być używany jako zmienna; jeden stan jest „prawdziwy”, a drugi „fałszywy”. Gadżet z dwoma stanami, który może być „długi”, może się zginać i dzielić, jest przydatny jako drut - jeśli może oddziaływać ze zmienną i zostać ograniczony do rozszerzenia stanu zmiennej do innej lokalizacji. Gadżet z dokładnie trzema stanami może być użyty jako klauzula; jeśli można go użyć do ograniczenia „jednego z trzech” drutów przez każdy z trzech stanów. Podobnie, można chcieć wszelkiego rodzaju bramek logicznych, takich jak nie-gadżet, or-gadżet, xor-gadżet itp .;

Blok konstrukcyjny

$\mathbf 1$ $\mathbf 1$
$\mathbf 1$ $\mathbf 1$
$\mathbf 1$
$\star$
$\star$ $\star$

wprowadź opis zdjęcia tutaj

$3$ $\mathbf{1}$ $\mathbf{(1,1)}$ $\mathbf{(1,1)}$

$4$ $5$ $\mathbf{(1,1)}$

Ściana

$4$

Obrazy poniżej, od lewej do prawej:

$\mathbf 1$
$\mathbf 1$
$\mathbf 1$
Linia ściany narysowana dla podkreślenia.

wprowadź opis zdjęcia tutaj

Pierwsza próba drutu

$\mathbf 1$

Pokazując tylko obramowania ścian, otrzymujemy to na poniższych rysunkach (od lewej do prawej):

Umieszczenie dwóch ścian naprzeciw siebie.
Wstawianie unikalnych liczb do środka.
Prawostronne dwa: dwa możliwe stany drutu.

wprowadź opis zdjęcia tutaj

Jak to działa:

W rurze / drucie nie może być żadnych otworów, dlatego jeśli płytki zostaną przesunięte do góry, wówczas wszystkie muszą zostać przesunięte do góry wzdłuż rury; jeśli zostaną przesunięte w dół, „zassie” je wszystkie. W ten sposób możemy wysłać „sygnał” z jednej strony drutu na drugą; innymi słowy, propaguj wartość.

Zatem teraz możemy propagować wartość na duże odległości!

Pozostałe ograniczenia to:

Nie możemy zgiąć drutu,
Nie możemy rozdzielić drutu,
Nie możemy krzyżować przewodów,
Możemy mieć irytujące problemy z układem, ponieważ musimy zachować ostrożność przy parzystości długości drutu.

Gięcie drutu , Część 1: Ściana poniżej

Kolejnym problemem jest to, że musimy być w stanie zgiąć drut, a nie tylko iść prosto ...

Więc. Część gnącą podzielimy na dwie części; górna część i dolna część. Najpierw dolna część. Zignoruj górną część zakrętu, zrobimy to później.

Poniższe rysunki pokazują trochę problemu z gięciem; górna część drutu jest „luźna”, trudno jest wykonać ścianę, która obraca się ostro o 90 stopni.

Z lewej na prawą:

Górna część drutu jest „luźna”.
Co się stanie, jeśli spróbujemy go zgiąć; chcemy, aby drut znajdował się między niebieskimi liniami. Ponownie zignoruj górną część zakrętu, zrobimy to później.
$\mathbf 1$

wprowadź opis zdjęcia tutaj

Jedno z rozwiązań jest następujące:

$\mathbf{(x,1)}$ $\mathbf x$ $\mathbf{ q \star}$ $\mathbf \star$ $\mathbf x$ $\mathbf 1$ $\mathbf 1$ $\mathbf 1$ $\mathbf 1$

Ilustracja poniżej, opis od lewej do prawej:

Sytuacja z problemem.
$\mathbf{q \star}$ $\mathbf 1$
$\mathbf 1$

wprowadź opis zdjęcia tutaj

$\mathbf {{q}{\star}}$ $\mathbf {{q}{\star}}$

Od lewej do prawej:

Obecna konstrukcja.
$\mathbf {{q}{\star}}$

wprowadź opis zdjęcia tutaj

$\mathbf 1$ $\mathbf 1$

$\mathbf{({r}{\star},1)}$ $\mathbf{r}{\star}$ $\mathbf 1$

Ilustracja poniżej, od lewej do prawej:

Nasza obecna konstrukcja.
$\mathbf 1$
$\mathbf{r}{\star}$ $\mathbf 1$

wprowadź opis zdjęcia tutaj

I w końcu otrzymujemy nasz dolny zakręt. Ilustracja poniżej, opisy, od lewej do prawej:

Po lewej: nasza ostateczna konstrukcja do zakrętu.
Po prawej: jak kontynuować drut po lewej stronie.

wprowadź opis zdjęcia tutaj

Gięcie drutu , część 2: Ściana powyżej

Ściany tworzące górny róg zakrętu są znacznie prostsze. Po prostu wyrównujesz ścianę pionową ze ścianą poziomą. Ilustracja poniżej, opis od lewej do prawej:

Gięcie drutu, które chcemy wykonać.
Umieść pionową część kwadratów ściany w dół.
Układanie kwadratów pionowej ściany.
Umieszczenie i układanie poziomej ściany; może spotkać pionową ścianę i utworzyć narożnik.

wprowadź opis zdjęcia tutaj

Teraz powinieneś być przekonany, że możemy umieszczać i zginać druty. Nadal nie możemy dzielić ani krzyżować drutów, więcej na ten temat później.

Pozostałe ograniczenia to:

~~Nie możemy zgiąć drutu,~~
Nie możemy rozdzielić drutu,
Nie możemy krzyżować przewodów,
Możemy mieć irytujące problemy z układem, ponieważ musimy zachować ostrożność przy parzystości długości drutu.

Cenny drut

$7$ $\star$ ${\mathcal T}{\star}$ ${\mathcal F}{\star}$ ${\mathcal T}{\star}$ ${\mathcal F}{\star}$ $\star$ kwadrat oddzielający je. Zilustrowane poniżej, opis od lewej do prawej:

Po lewej: drut.
Po prawej: konfiguracja kwadratowa.

wprowadź opis zdjęcia tutaj

${\mathcal T}{\star}$ ${\mathcal F}{\star}$

Lewy, prawy: dwa stany wycenionego drutu ;
${\mathcal T}{\star}$
${\mathcal F}{\star}$

wprowadź opis zdjęcia tutaj

${\rm 3\text{-}S{\small AT}}$

Pozostałe ograniczenia to:

Nie możemy rozdzielić drutu,
Nie możemy krzyżować przewodów,
Możemy mieć irytujące problemy z układem, ponieważ musimy zachować ostrożność przy parzystości długości drutu.

Nie-brama

Nie-gate jest niepotrzebna, ponieważ jest niejawny: po prostu za pomocą off-by-one o długości drutu możemy negować wartość drutu.

Brama klauzulowa

$3$

Ilustracje poniżej, opisy od lewej do prawej:

Układ drutowy gadżetu klauzulowego. To robi znak „plus”; połączenie 3 drutów w jednym miejscu.
$\star$
${\rm 1\text{-in-}3\text{-}S{\small AT}}$

wprowadź opis zdjęcia tutaj

Teraz spójrzmy na różne stany. Ilustracja poniżej, opis od lewej do prawej:

Lewy drut jest wciągany do środka; pozostałe dwie są wypchnięte.
Drut dolny jest wciągany do środka; pozostałe dwie są wypchnięte.
Prawy dolny drut jest wciągany do środka; pozostałe dwie są wypchnięte.

wprowadź opis zdjęcia tutaj

$3$ $1\text{-in-}3$

Pozostałe ograniczenia to:

Nie możemy rozdzielić drutu,
Nie możemy krzyżować przewodów,
Możemy mieć irytujące problemy z układem, ponieważ musimy zachować ostrożność przy parzystości długości drutu.

Podział drutu

${\mathcal T}{\star}$ ${\mathcal T}{\star}$ ${\mathcal T}{\star}$ ${\mathcal T}_1{\star}$ ${\mathcal T_2}{\star}$ $\star$ $a{\star},b{\star},c{\star}$ $\star$ $a{\star},b{\star},c{\star}$ ${\mathcal T}{\star}$ $\star$ $a{\star},b{\star},c{\star}$

Ilustracja poniżej, opis od lewej do prawej:

Układ przewodów. Zwróć uwagę, że ściany są nieco grube, więc druty są przybliżone do siebie w celach ilustracyjnych; w rzeczywistości są nieco dalej.
${\mathcal T}{\star}$ $a{\star},b{\star},c{\star}$

wprowadź opis zdjęcia tutaj

$a{\star},b{\star}$ $a{\star},b{\star}$ $a{\star},b{\star}$

Przykładowy stan lewego drutu o wartości true.
Zły stan drugiego drutu; próbuje być inaczej wyceniony, ale potem otrzymuje zduplikowaną parę.
Dobry stan drugiego drutu, teraz mają tę samą wartość i nie ma zduplikowanych par.

wprowadź opis zdjęcia tutaj

$a{\star},b{\star},c{\star}$

Pozostałe ograniczenia to:

~~Nie możemy rozdzielić drutu,~~
Nie możemy krzyżować przewodów,
Możemy mieć irytujące problemy z układem, ponieważ musimy zachować ostrożność przy parzystości długości drutu.

Przewód bezprzewodowy!

Cóż, ku mojej radości, przecięcie drutu okazało się bezprzewodowe! Oznacza to, że na powyższych ilustracjach kładę druty obok siebie, ale nie ma powodu! Możemy umieścić przewody w dowolnym miejscu na siatce, a one nadal byłyby „splątane”, że tak powiem. To oszczędza nam wielu problemów:

${\rm\mathbf{3\text{-} S{\small AT}}}$
Musimy zrobić każdy irytujący układ, doprowadzając przewody do ich lokalizacji, to proste! Jak telefon bezprzewodowy! Wolność!
Nie musimy się martwić o parytet długości drutu / układ off-by-one.
Możemy dokonać dość minimalnej redukcji; każda zmienna otrzyma pojedynczy zestaw długich pasków drutu z dużą ilością bezprzewodowych połączeń wzdłuż przewodów. Połączenia te będą do bramek-klauzul, które będą znajdować się we własnej lokalizacji na siatce. Klauzula będzie teraz składać się tylko z gadżetu klauzuli i trzech wystających z niej przewodów bezprzewodowych.

Pozostałe ograniczenia to:

~~Nie możemy krzyżować przewodów,~~
~~Możemy mieć irytujące problemy z układem, ponieważ musimy zachować ostrożność przy parzystości długości drutu.~~

Redukcja, pierwsza próba

$\Phi(\mathbf x)= \bigwedge_i C_i$ $1\text{-in-}3\text{-}{\rm S{\small AT}}$

$x_j \in \mathbf x$
$C_i \in \Phi(\mathbf x)$
$x_j$ $C_i$ $3$ $a{\star},b{\star},c{\star}$

Jak może to wyglądać:

$a{\star},b{\star},c{\star}$

wprowadź opis zdjęcia tutaj

Oto, jak mogłaby wyglądać siatka:

Rys.: Powstała plansza. Zmienne są ułożone w rzędach na dole. Klauzule są rozłożone na górze. Ten układ daje kwadratowy wybuch; mądrzejszy układ pozwala uniknąć kwadratowego wybuchu.

wprowadź opis zdjęcia tutaj

Szczegóły w ostatniej chwili

Przypomnij sobie problem decyzyjny:

$(n+1) \times (n+2)$ $n$

$(n+1) \times (n+2)$ $n$ $\mathcal O(n)$

$\mathcal O\left(|\mathbf x|\times \left|\Phi(\mathbf x)\right|\right)$ $\in \mathcal O\left(n\right)$ $n$
Innym, bardziej zwięzłym, bardziej złożonym sposobem jest dywersyfikacja $\mathbf 1$ $\mathcal O(n)$

Źródła wykresów

— Realz Slaw
źródło

[a_{i}, b_{i}]

$[a_i,b_i]$

a_{i}, b_{i} = 1.. n

$a_i,b_i=1..n$

Przeniosę wszystkie te komentarze do mojej odpowiedzi i sprawię, że będą bardziej wyczerpujące w mojej kolejnej dużej wersji.

— Realz Slaw

ok, poczekam na to!

— Vor

@RealzSlaw, bardzo dziękuję! Nadal nie miałem czasu, aby to przeczytać, ale wygląda to bardzo ładnie.

— Yoav bar sinai

@RealzSlaw, czy istnieje sposób, aby skontaktować się z Tobą bezpośrednio?

— Yoav bar sinai

Czy Dominosa NP-Hard?

Problemy z redukcją

Wymuszanie gadżetu

Nowe bramy drutowe i klauzulowe

Zastrzeganie i F.T.T\mathcal TfaF\mathcal F

Drut

Klauzula

Sformułowanie

Źródła TikZ

D O M I N O S ADOMINOSA{\rm D{\small OMINOSA}}

1 - 3- in- S A T1-3-in-SAT1\text{-}3\text{-in-}{\rm S{\small AT}}D O M I N O S ADOMINOSA{\rm D {\small OMINOSA}}

Wprowadzenie

Blok konstrukcyjny

Ściana

Pierwsza próba drutu

Gięcie drutu , Część 1: Ściana poniżej

Gięcie drutu , część 2: Ściana powyżej

Cenny drut

Nie-brama

Brama klauzulowa

Podział drutu

Przewód bezprzewodowy!

Redukcja, pierwsza próba

Szczegóły w ostatniej chwili

Źródła wykresów

Zastrzeganie i $\mathcal T$ $\mathcal F$

${\rm D{\small OMINOSA}}$

$1\text{-}3\text{-in-}{\rm S{\small AT}}$ ${\rm D {\small OMINOSA}}$