Niedeterministyczna logika ograniczeń

W informatyce teoretycznej niedeterministyczna logika ograniczeń to system kombinatoryczny, w którym orientacja jest nadawana krawędziom ważonego grafu nieskierowanego , z zastrzeżeniem pewnych ograniczeń. Można zmienić tę orientację etapami, w których pojedyncza krawędź jest odwrócona, z zastrzeżeniem tych samych ograniczeń. Udowodniono, że problem logiki ograniczeń i jego warianty są PSPACE - zupełne aby określić, czy istnieje sekwencja ruchów, która odwraca określoną krawędź i jest bardzo przydatna do pokazania, że ​​różne gry i łamigłówki są PSPACE-trudne lub PSPACE-kompletne.

Jest to forma odwracalnej logiki , w której każdą sekwencję zmian orientacji krawędzi można cofnąć. Twardość tego problemu została wykorzystana do udowodnienia, że ​​wiele gier i łamigłówek ma wysoką złożoność .

Wykresy ograniczeń

Bramka AND w logice z ograniczeniami. Ponieważ minimalny stopień węzłowy węzła wynosi 2, górna krawędź może być na zewnątrz wtedy i tylko wtedy, gdy dwie dolne krawędzie są w środku.

Przykład wykresu ograniczeń.

W najprostszej wersji niedeterministycznej logiki ograniczeń każda krawędź nieskierowanego grafu ma wagę jeden lub dwa. (Wagi można również przedstawić graficznie, rysując krawędzie wagi 1 na czerwono, a krawędzie wagi 2 na niebiesko ) . do parzystej liczby czerwonych krawędzi.

Krawędzie muszą być zorientowane w taki sposób, aby co najmniej dwie jednostki wagi były zorientowane w kierunku każdego wierzchołka: musi być albo co najmniej jedna przychodząca niebieska krawędź, albo co najmniej dwie przychodzące czerwone krawędzie. Orientację można zmieniać etapami, w których pojedyncza krawędź jest odwracana, z poszanowaniem tych ograniczeń.

Bardziej ogólne formy niedeterministycznej logiki ograniczeń pozwalają na większą różnorodność wag krawędzi, więcej krawędzi na wierzchołek i różne progi określające, jaką wagę musi mieć każdy wierzchołek. Graf z systemem wag krawędzi i progów wierzchołków nazywany jest grafem z ograniczeniami . Ograniczony przypadek, w którym wszystkie wagi krawędzi wynoszą jeden lub dwa, wierzchołki wymagają dwóch jednostek wagi przychodzącej, a wszystkie wierzchołki mają trzy incydentne krawędzie z parzystą liczbą czerwonych krawędzi, nazywane są grafami ograniczeń i / lub .

Powodem istnienia grafów nazw i/lub ograniczeń jest to, że dwa możliwe typy wierzchołków w grafie i/lub grafach ograniczeń zachowują się w pewien sposób jak bramka AND i bramka OR w logice boolowskiej . Wierzchołek z dwiema czerwonymi krawędziami i jedną niebieską zachowuje się jak bramka AND, ponieważ wymaga, aby obie czerwone krawędzie były skierowane do wewnątrz, zanim niebieska krawędź będzie skierowana na zewnątrz. Wierzchołek z trzema niebieskimi krawędziami zachowuje się jak bramka OR, z dwiema krawędziami wyznaczonymi jako wejściowe, a trzecią jako wyjściową, ponieważ wymaga, aby co najmniej jedna krawędź wejściowa była skierowana do wewnątrz, zanim krawędź wyjściowa będzie skierowana na zewnątrz.

Zazwyczaj problemy z logiką ograniczeń są definiowane wokół znajdowania prawidłowych konfiguracji wykresów ograniczeń. Grafy ograniczeń to grafy nieskierowane z dwoma rodzajami krawędzi:

• czerwone krawędzie z ciężarem ${\ displaystyle 1}$
• niebieskie krawędzie z wagą ${\ displaystyle 2}$

Używamy grafów z ograniczeniami jako modeli obliczeniowych, w których myślimy o całym grafie jako o maszynie. Konfiguracja maszyny składa się z wykresu wraz z określoną orientacją jego krawędzi. Konfigurację nazywamy prawidłową, jeśli spełnia ograniczenie napływu: każdy wierzchołek musi mieć przychodzącą wagę co najmniej ${\ displaystyle 2}$ . Innymi $słowy$ , suma wag krawędzi wchodzących do danego wierzchołka musi być co najmniej niż suma wag krawędzi wychodzących z wierzchołka.

Definiujemy również ruch na grafie ograniczeń jako działanie polegające na odwróceniu orientacji krawędzi, tak aby wynikowa konfiguracja była nadal poprawna.

Formalna definicja problemu logiki ograniczeń

Załóżmy, że mamy dany wykres ograniczeń, konfigurację początkową i konfigurację końcową. Ten problem polega na pytaniu, czy istnieje sekwencja prawidłowych ruchów, które przenoszą go z konfiguracji początkowej do konfiguracji końcowej. Redukcja wynika z QSAT i została przedstawiona poniżej.

Warianty

Planarna niedeterministyczna logika ograniczeń

Powyższy problem jest PSPACE-Complete nawet jeśli graf ograniczeń jest planarny , tzn. żaden graf nie może być narysowany w taki sposób, że żadne dwie krawędzie się nie przecinają. Ta redukcja wynika z Planar QSAT .

Odwrócenie krawędzi

Ten problem jest szczególnym przypadkiem poprzedniego. Pyta, biorąc pod uwagę wykres ograniczeń, czy możliwe jest odwrócenie określonej krawędzi za pomocą sekwencji prawidłowych ruchów. Zauważ, że można to zrobić za pomocą sekwencji prawidłowych ruchów, o ile ostatni ważny ruch odwraca pożądaną krawędź. Udowodniono również, że ten problem jest PSPACE-Complete dla wykresów 3-regularnych lub 3-stopniowych.

Zadowolenie z wykresu ograniczeń

Ten problem polega na pytaniu, czy istnieje orientacja krawędzi, która spełnia ograniczenia dopływu, biorąc pod uwagę niekierowany wykres ${\ displaystyle G}$ . Udowodniono, że ten problem jest NP-zupełny.

Trudne problemy

Następujące problemy, dotyczące i/lub grafów ograniczeń i ich orientacji, są PSPACE-zupełne:

• Biorąc pod uwagę orientację i określoną krawędź e , sprawdzanie, czy istnieje sekwencja kroków od podanej orientacji, która ostatecznie odwraca krawędź e .
• Testowanie, czy jedną orientację można zmienić na inną za pomocą sekwencji kroków.
• Biorąc pod uwagę dwie krawędzie e i f o określonych kierunkach, sprawdzamy, czy dla całego wykresu istnieją dwie orientacje, z których jedna ma określony kierunek na e , a druga ma określony kierunek na f , które można przekształcić w siebie w sekwencji kroków .

Dowód, że te problemy są trudne, polega na redukcji z kwantyfikowanych formuł boolowskich , opartych na logicznej interpretacji i/lub wykresach ograniczeń. Wymaga dodatkowych gadżetów do symulacji kwantyfikatorów i konwersji sygnałów przenoszonych na czerwonych krawędziach na sygnały przenoszone na niebieskich krawędziach (lub odwrotnie), co można osiągnąć za pomocą kombinacji wierzchołków and i or.

Problemy te pozostają PSPACE-zupełne nawet dla grafów i/lub grafów z ograniczeniami, które tworzą grafy planarne . Dowodem na to jest konstrukcja gadżetów typu crossover, które umożliwiają krzyżowanie się dwóch niezależnych sygnałów. Możliwe jest również nałożenie dodatkowego ograniczenia, przy jednoczesnym zachowaniu twardości tych problemów: każdy wierzchołek z trzema niebieskimi krawędziami może wymagać, aby był częścią trójkąta z czerwoną krawędzią. Taki wierzchołek nazywamy chronionym lub i ma tę właściwość, że (w dowolnej prawidłowej orientacji całego wykresu) nie jest możliwe, aby obie niebieskie krawędzie trójkąta były skierowane do wewnątrz. To ograniczenie ułatwia symulowanie tych wierzchołków w redukcji twardości dla innych problemów. Dodatkowo, grafy ograniczeń mogą wymagać ograniczonej przepustowości , a problemy na nich nadal pozostaną PSPACE-complete.

Dowód twardości PSPACE

Redukcja wynika z QSAT. Aby osadzić formułę QSAT, musimy utworzyć gadżety AND, OR, NOT, UNIVERSAL, EXISTENTIAL i Converter (aby zmienić kolor) na wykresie ograniczeń. Pomysł przebiega następująco:

• Wierzchołek AND to taki wierzchołek, który ma dwie incydentne czerwone krawędzie (wejścia) i jedną niebieską krawędź incydentu (wyjście).
• Wierzchołek OR to taki wierzchołek, który ma trzy przypadkowe niebieskie krawędzie (dwa wejścia, jedno wyjście).

W ten sposób można również tworzyć inne gadżety. Pełna konstrukcja jest dostępna na stronie Erika Demaine'a . Pełna konstrukcja jest również wyjaśniona w sposób interaktywny.

Aplikacje

Oryginalne zastosowania niedeterministycznej logiki ograniczeń wykorzystywały ją do udowodnienia kompletności PSPACE przesuwanych łamigłówek, takich jak Godziny szczytu i Sokoban . Aby to zrobić, wystarczy pokazać, jak symulować krawędzie i orientacje krawędzi oraz wierzchołki i wierzchołki chronione lub wierzchołki w tych układankach.

Niedeterministyczna logika ograniczeń została również wykorzystana do udowodnienia twardości rekonfiguracyjnych wersji klasycznych problemów optymalizacji grafów, w tym zbioru niezależnego , pokrycia wierzchołków i zbioru dominującego , na płaskich grafach o ograniczonej przepustowości. W tych problemach należy zmienić jedno rozwiązanie danego problemu na inne, przesuwając po jednym wierzchołku naraz do lub z zestawu rozwiązań, zachowując właściwość, że przez cały czas pozostałe wierzchołki tworzą rozwiązanie.

Rekonfiguracja 3SAT

Biorąc pod uwagę formułę 3-CNF i dwa satysfakcjonujące przypisania, ten problem pyta, czy możliwe jest znalezienie sekwencji kroków, które zaprowadzą nas od jednego przypisania do drugiego, gdzie w każdym kroku możemy odwrócić wartość zmiennej. Ten problem można pokazać jako PSPACE-zupełny poprzez redukcję z problemu niedeterministycznej logiki ograniczeń.

Puzzle z przesuwanymi klockami

Ten problem polega na pytaniu, czy możemy osiągnąć pożądaną konfigurację w przesuwanej układance blokowej, biorąc pod uwagę początkową konfigurację bloków. Ten problem jest PSPACE-zupełny, nawet jeśli prostokąty są kostkami domina.

Godziny szczytu

Ten problem dotyczy tego, czy możemy osiągnąć warunek zwycięstwa układanki godziny szczytu , biorąc pod uwagę początkową konfigurację. Ten problem jest PSPACE-zupełny, nawet jeśli bloki mają rozmiar ${\ displaystyle 1 \ razy 2}$ .

Dynamiczne etykietowanie mapy

Biorąc pod uwagę statyczną mapę, ten problem pyta, czy istnieje płynne dynamiczne etykietowanie. Ten problem jest również PSPACE-zupełny.