Czy ta klasyczna gra z układankami NP-zupełna?

Istnieje klasyczna gra logiczna, bardzo podobna do krzyżówki, z tą różnicą, że podana jest lista słów, a następnie podana jest kwadratowa tablica złożona z kwadratów jednostkowych, z niektórymi kwadratami zaciemnionymi jak krzyżówka, a na niektórych kwadratach jest już napisany list. Celem jest zapisanie każdego słowa z listy raz i tylko raz w układance, gdzie każde słowo jest zapisywane poziomo (od lewej do prawej) lub pionowo (z góry na dół) na nie zaciemnione kolejne kwadraty i podczas pisania słowa , dwa kwadraty otaczające końce słowa muszą być zaciemnione lub wyłączone z planszy. Również w przypadku liter zapisanych wcześniej na niektóre kwadraty słowa, które pokrywają się z tymi kwadratami, muszą być zgodne z literą wcześniej napisaną.$N \times N$

Teraz, jeśli przyjmiemy stały alfabet dla słów, decydujemy, czy możemy wypełnić tablicę prawidłowym rozwiązaniem, używając dokładnie każdego słowa na liście tylko raz, i tylko raz problem NP-zupełny, jeśli długość boku deski wynosi nie naprawiony?

Przepraszamy za odpowiedź na stary post.

Zastanawiałem się nad tym i myślę, że problem ze stałym alfabetem jest również NP-zupełny.

Mam zamiar zredukować pozytywny 1-w-3 SAT do tego problemu słownego

Wczoraj miałem problemy ze znalezieniem pomysłów na rozwiązanie problemu. Miałem problem z odróżnieniem każdej zmiennej, dopóki nie spojrzałem ponownie na pytanie i zdałem sobie sprawę, że pozwoliłeś mieć kwadraty z posadzonymi symbolami. To znacznie uprościło redukcję. Innym moim pomysłem było stworzenie słów o różnej długości dla każdej zmiennej.

REDUKCJA

Teraz opiszę gadżety, których będziemy używać:

Zmienny gadżet

Każdą zmienną oznaczamy innym indeksem liczbowym i dla każdej zmiennej będziemy mieć inną liczbę. Wybieramy największy indeks i reprezentujemy liczbę w formacie binarnym, nazwiemy ten łańcuch binarny .$n$

Następnie tworzymy dwa różne słowa pionowe dla każdej zmiennej. Wszystkie słowa będą miały długość(Tylko jeśli zezwalamy na powielanie słów na liście słów), gdziejest długością łańcucha binarnego .| n | $3 + |n|$$|n|$$n$

Na przykład, niech największym indeksem będzie liczba . Kiedy przekształcamy tę liczbę na binarną, otrzymujemy łańcuch w postaci binarnej, łańcuch ten ma długość trzy. Tak więc każde słowo zmienne będzie miało w tym przykładzie długość .100 $4$$100$$6$

Teraz tworzymy dwa różne słowa dla każdej zmiennej. Jedno słowo będzie miało symbol na początku, następnie symbol poniżej, a następnie łańcuch binarny, który reprezentuje indeks zmiennej, a my zerujemy łańcuch tak, aby miał taką samą długość jak łańcuch a na końcu symbol na końcu. Oczywiście symbole można zmienić.2 n $3$$2$$n$$3$

Drugie słowo jest prawie takie samo, ale będzie miało symbol zamiast symbolu .$4$$3$

Na przykład, niech największym indeksem będzie liczba . Będziemy mieć dwa następujące słowa dla zmiennej o indeksie :$4$$1$

$320013$ i$420014$

Jak widzimy, dopełniamy binarną reprezentację liczby zerami, aby miała długość| n $1$$|n|$

Musimy skopiować te słowa wiele razy, potrzebujemy jednej kopii każdego słowa na każde wystąpienie zmiennej w instancji SAT. Spowoduje to utworzenie duplikatów na liście słów. Możemy pozbyć się duplikatów, dodając kolejny łańcuch binarny do łańcucha binarnego, który jednoznacznie identyfikuje zmienną. Ten nowy łańcuch jednoznacznie identyfikuje każdą wystąpienie zmiennej.

Aby to zrobić, po prostu przypisujemy każdemu wystąpieniu zmiennej inny łańcuch binarny i olacy ten łańcuch na końcu binarnej reprezentacji zmiennej.

Aby utworzyć ten nowy łańcuch binarny, najpierw musimy utworzyć inny indeks dla każdej zmiennej, nazywamy największą liczbą w każdym indeksie gdzie jest identyfikatorem dla każdej zmiennej. Następnie przekształcamy liczbę w łańcuch binarny, a następnie liczymy długość łańcucha, nazywamy ten numer. Następnie dla każdego indeksu tworzymy inną liczbę binarną dla każdej wystąpienia zmiennej. Wpisujemy liczbę zerami, aż długość łańcucha binarnego stanie siętak aby wszystkie słowa należące do każdej wystąpienia zmiennej miały tę samą długość. i n i | n i | | n i $n_i$$i$$n_i$$|n_i|$$|n_i|$

Pozwoli to pozbyć się duplikatów w słowach zmiennych.

Załóżmy na przykład, że zmienna pojawia się trzy razy w instancji SAT. Tworzymy następujące słowa:$x_2$

42010014 32010103 42010104 32010113 $32010013$ $42010014$ , i$32010103$ $42010104$$32010113$ $42010114$

Gadżet klauzuli

Dla każdego gadżetu klauzuli utworzymy trzy nowe wyrazy poziome, każde słowo klauzuli będzie miało długość kwadratów (tylko jeśli zezwolimy na powielanie słów na liście słów). Oto słowa, które stworzymy dla każdej klauzuli:$6$

535453 $535354$ , i$535453$$545353$

Mamy inne słowo klauzuli dla każdego możliwego sposobu wypełnienia zdania, symbol reprezentuje literalny zbiór wartości true, a symbol reprezentuje literalny zbiór wartości false. Liczba służy do wskazania, że ​​jest to słowo klauzulowe.3 $4$$3$$5$

Powtórzą się słowa na liście słów, możemy się ich pozbyć, stosując procedurę, której użyliśmy do jednoznacznej identyfikacji słów zmiennych. Oznacza to, że tworzymy inny łańcuch binarny dla każdej klauzuli i dołączamy każdy łańcuch do słów klauzuli odpowiadających każdej klauzuli. Aby to zrobić, tworzymy nowy indeks klauzul i wybieramy największą liczbę indeksu, nazwiemy ten numer . Reprezentujemy jako łańcuch binarny i nazywamy długość tego łańcucha binarnego jako. Teraz tworzymy inną liczbę binarną dla każdej klauzuli, zaczynając od liczby 1, i wpisujemy liczbę zerami, aby utworzyć łańcuch binarny o długościm | m | | m $m$$m$$|m|$$|m|$. Dołączamy każdy łańcuch binarny do słów klauzuli, które należą do klauzuli.

Teraz zobaczmy na tablicy zdjęcie gadżetu klauzulowego:

Ten przykład reprezentuje klauzulę a redukowana instancja 1 na 3 to( x 1 ∨ x 2 ∨ x 3 ) ∧ ( x 2 ∨ x 3 ∨ x 4$(x_2 \lor x_3 \lor x_4)$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

Jak widzimy, są zapisane kwadraty. Pionowe kolumny mają zapisane symbole wskazujące, które literały znajdują się w klauzuli. Koniec i początek kolumny to puste kwadraty. Pozwala to graczowi wybrać wartość zmiennej. Oznaczone symbole w poziomym rzędzie zmuszają gracza do wstawienia słowa klauzulowego w tym rzędzie. Ponieważ wszystkie słowa klauzul mają tylko jeden symbol co oznacza, że ​​tylko jeden z literałów znajdujących się w gadżecie klauzul może być ustawiony na „prawda”.$4$

Jeśli nie pozwolimy na duplikaty na liście słów, będziemy musieli zmodyfikować obraz.

Wiersz klauzuli na obrazie będzie : a literalne kolumny będą od lewej do prawej:$5b5b5b10$

b 201110 b b 21001 $b201010b$ , i$b201110b$$b21001b$

Gdzie symbol oznacza pusty kwadrat$b$

Zobacz przykład:

Gadżet o zmiennej spójności

Jest to gadżet, który zapewnia, że ​​gracz może przypisać tylko tę samą wartość dla wszystkich literalnych kolumn zmiennej.

Będziemy mieć nowy gadżet dla każdej zmiennej

Dla każdego gadżetu utworzymy dwa nowe słowa.

Długość słowa będzie zależeć od liczby wystąpień zmiennej. Długość słowa będzie wynosić gdzie jest liczbą wystąpień zmiennej. Jeśli więc zmienna pojawi się dwa razy w instancji sat, słowa będą miały długość czterech. Jedno z dwóch słów powstaje przez powtórzenie łańcucha razy, gdzie k jest liczbą wystąpień zmiennej. Drugie słowo powstaje przez powtórzenie łańcucha razy, gdzie k jest liczbą wystąpień zmiennej w instancji SAT, która jest zmniejszana.$2 * k$$k$$x_2$$63$ $k$$64$ $k$

Na przykład, jeśli zmienna ma dwie częstotliwości, słowa należące do odpowiedniego gadżetu przypisania zmiennej to:$x_2$

$6363$ i$6464$

Jeśli chcemy uniknąć powtarzania słów, zauważ, że każdy gadżet spójności należy do innej zmiennej. Możemy więc dołączyć łańcuch binarny identyfikujący każdą zmienną do dwóch słów, które stworzyliśmy dla tego gadżetu.

Zobaczmy teraz przykładowe zdjęcie tego gadżetu:

Ten gadżet dotyczy zmiennej a redukowana instancja 1 na 3 to .$x_2$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

Jak widzimy, istnieją dwa poziome rzędy, symbole zapisane w rzędach zapewniają, że możemy umieszczać tylko słowa zawierające te symbole, te słowa są słowami, które stworzyliśmy dla tego gadżetu. W jednym z wierszy widzimy, że wchodzą do niego dwie kolumny, ponieważ ze względu na symbole umieszczone w kolumnach upewniamy się, że możemy umieszczać tylko słowa zmienne. Ponieważ jedyne słowa, które możemy umieścić tylko w rzędzie o zmiennej konsystencji, zawierają tylko symbol lub tylko symbol , zmuszamy gracza do umieszczenia wszystkich gadżetów o tym symbolu wewnątrz gadżetu. Oznacza to, że jedyne zmienne słowa, które można umieścić w gadżetach klauzul, mają tylko symbol lub tylko symbol$3$$4$$3$$4$. Możemy umieścić pozostałe słowo tego gagdeta w drugim rzędzie

Jeśli nie zezwalamy na duplikaty na liście słów, słowa w przykładowym obrazie będą następujące:

Dla rzędów:

$6b6b010$ i$6b6b010$

Dla kolumn:

$b201001b$ i$b201010b$

Gdzie symbol oznacza pusty kwadrat$b$

Zobacz przykład:

Gadżet zrzutu zrzutu

Jest to gadżet stworzony do umieszczania nieużywanych słów w klauzulach. Aby to zrobić, musimy umieścić tylko dwa wiersze dla każdego słowa klauzuli w pustej części tablicy. Te rzędy nie są połączone z żadnym innym rzędem ani kolumną.

Dzięki temu kończymy redukcję, ponieważ twierdziliśmy, że potrzebujemy tylko 6 symboli do redukcji.

Przykład

Jeśli poprzednie wyjaśnienie było mylące, oto przykładowy przykład dodatniej 1 na 3 SAT, który został zredukowany do tego problemu słownego:

Jeśli zabronimy powtarzania słów:

Instancja, która została zmniejszona to:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

Myślę, że działa następująca redukcja z Directed Hamiltonian path:

Biorąc pod uwagę wykres i dwa wierzchołki , otrzymujemy następującą łamigłówkę:$G=(V,E)$$s,t\in V$

Alfabet jest , z są niektóre nie symbol .$V\cup \{*\}$$*$$V$

Słowa są dla każdego i dla każdej krawędzi .$v*v$$v\in V$$vu$$(u,v)\in E$

Tablica składa się z dwóch części. Pierwszy wygląda jakpoziome „schody” o długości 3, ułożone jeden na drugim, jak pokazano tutaj:$|V|$

Druga część składa się z rozłącznych przestrzeni o długości 2.$|E|-(|V|-1)$

Ponadto ustawiamy w pierwszym (dolnym) stopniu schodów słowo (i usuwamy je z listy słów), aw ostatnim kroku umieszczamy .t ∗ $s*s$$t*t$

Teraz, aby wypełnić schody, w schodach można wstawiać tylko słowa wierzchołków, a aby połączyć dwa wierzchołki, należy umieścić między nimi słowo krawędzi, które odpowiada istniejącej krawędzi na wykresie. Niewykorzystane krawędzie można umieścić w drugiej części planszy. Drugi kierunek jest trywialny.

Myślę, że to działa (naszkicowany przeze mnie dowód poprawności jest w najlepszym razie machany ręcznie, ale nadal).