Gadżet (informatyka)
W teorii złożoności obliczeniowej gadżet jest podzbiorem wystąpienia problemu, który symuluje zachowanie jednej z podstawowych jednostek innego problemu obliczeniowego . Gadżety są zwykle używane do konstruowania redukcji z jednego problemu obliczeniowego do drugiego, jako część dowodów NP-zupełności lub innych rodzajów twardości obliczeniowej. Technika projektowania komponentów to metoda konstruowania redukcji za pomocą gadżetów.
Szabó (2009) śledzi użycie gadżetów w artykule WT Tutte z 1954 r. W teorii grafów , w którym Tutte dostarczył gadżetów do zredukowania problemu znalezienia podgrafu z określonymi ograniczeniami stopnia do problemu idealnego dopasowania . Jednak terminologia „gadżetów” ma późniejsze pochodzenie i nie pojawia się w artykule Tutte.
Przykład
Wiele dowodów NP-zupełności opiera się na redukcjach wiele-jeden z 3-spełnialności , problemie znalezienia satysfakcjonującego przypisania do formuły boolowskiej, która jest koniunkcją (logiczna i) klauzul, przy czym każda klauzula jest dysjunkcją (boolowska lub) trzech terminy, a każdy termin jest zmienną boolowską lub jej zaprzeczeniem. Redukcja tego problemu do trudnego problemu na grafach nieskierowanych , takich jak problem cyklu Hamiltona lub kolorowanie grafów , zazwyczaj byłaby oparta na gadżetach w postaci podgrafów, które symulują zachowanie zmiennych i klauzul danej instancji 3-spełnialności . Te gadżety byłyby następnie sklejane, tworząc pojedynczy wykres, trudny przypadek rozważanego problemu z wykresem.
0 Na przykład problem testowania 3-koloryzowalności grafów można udowodnić jako NP-zupełny przez redukcję z 3-spełnialności tego typu. Redukcja wykorzystuje dwa specjalne wierzchołki wykresu, oznaczone jako „Ground” i „False”, które nie są częścią żadnego gadżetu. Jak pokazano na rysunku, gadżet dla zmiennej x składa się z dwóch wierzchołków połączonych w trójkąt z wierzchołkiem podstawy; jeden z dwóch wierzchołków gadżetu jest oznaczony jako x , a drugi przez negację x . Gadżet dla klauzuli 0 ( t ∨ t 1 ∨ t 2 ) składa się z sześciu wierzchołków połączonych ze sobą wierzchołkami reprezentującymi wyrazy t , t 1 i t 2 oraz wierzchołkami podstawowymi i fałszywymi pokazanymi krawędziami . Dowolną 3-CNF można przekształcić w wykres, konstruując osobny gadżet dla każdej z jej zmiennych i klauzul i łącząc je, jak pokazano.
W dowolnym 3-kolorowym grafie wynikowym można oznaczyć trzy kolory jako prawdziwe, fałszywe lub podstawowe, gdzie fałszywe i podstawowe to kolory nadane fałszywym i podstawowym wierzchołkom (koniecznie różne, ponieważ wierzchołki te sąsiadują ze sobą przez konstrukcja), a prawdziwy jest pozostały kolor nieużywany przez żaden z tych wierzchołków. W gadżecie zmiennej możliwe są tylko dwa kolory: wierzchołek oznaczony zmienną musi mieć kolor prawdziwy lub fałszywy, a wierzchołek oznaczony negacją zmiennej musi odpowiednio mieć kolor fałszywy lub prawdziwy. W ten sposób prawidłowe przypisania kolorów do gadżetów zmiennych odpowiadają jeden do jednego przypisaniom prawdy do zmiennych: zachowanie gadżetu w odniesieniu do kolorowania symuluje zachowanie zmiennej w odniesieniu do przypisania prawdy. Każde przypisanie klauzuli ma ważne 3-kolorowe, jeśli co najmniej jeden z sąsiednich wierzchołków terminów ma kolor prawdziwy i nie może być 3-kolorowe, jeśli wszystkie sąsiednie wierzchołki terminów mają kolor fałszywy. W ten sposób gadżet klauzuli można pokolorować wtedy i tylko wtedy, gdy odpowiednie przypisanie prawdy spełnia klauzulę, więc ponownie zachowanie gadżetu symuluje zachowanie klauzuli.
Redukcje ograniczone
Agrawala i in. (1997) rozważyli coś, co nazwali „radykalnie prostą formą redukcji gadżetów”, w której każdy bit opisujący część gadżetu może zależeć tylko od ograniczonej liczby bitów danych wejściowych, i wykorzystali te redukcje, aby udowodnić analogię Bermana – Hipoteza Hartmanisa stwierdzająca, że wszystkie zbiory NP-zupełne są izomorficzne w czasie wielomianowym.
00 Standardowa definicja NP-zupełności obejmuje wielomianowe redukcje w czasie wielomianowym : problem w NP jest z definicji NP-zupełny, jeśli każdy inny problem w NP ma tego typu redukcję, a standardowy sposób udowodnienia, że problem w NP NP jest NP-zupełne polega na znalezieniu wielomianowej redukcji o wiele jeden ze znanego problemu NP-zupełnego do niego. Ale (w tym, co Agrawal i wsp. Nazwali „ciekawym, często obserwowanym faktem”) wszystkie zbiory, o których wiadomo, że były NP-zupełne w tamtym czasie, można było udowodnić, że są kompletne, używając silniejszego pojęcia redukcji AC wiele do jednego: to znaczy redukcji, które 0 mogą być obliczane za pomocą obwodów o rozmiarze wielomianu, stałej głębokości i nieograniczonym wachlarzu. Agrawala i in. udowodnił, że każdy zbiór, który jest NP-zupełny przy redukcji AC, jest kompletny przy jeszcze bardziej ograniczonym typie redukcji, NC 0 redukcjach wiele-jeden, przy użyciu obwodów o rozmiarze wielomianu, stałej głębokości i ograniczonym wachlarzu. W redukcji NC każdy bit wyjściowy redukcji może zależeć tylko od stałej liczby bitów wejściowych,
0000 Hipoteza Bermana – Hartmanisa jest nierozwiązanym problemem w teorii złożoności obliczeniowej, zgodnie z którym wszystkie klasy problemów NP-zupełnych są izomorficzne w czasie wielomianowym. Oznacza to, że jeśli A i B są dwiema NP-zupełnymi klasami problemów, istnieje wielomianowa redukcja jeden do jednego z A do B , której odwrotność jest również obliczalna w czasie wielomianowym. Agrawala i in. wykorzystał ich równoważność między redukcjami AC i redukcjami NC, aby pokazać, że wszystkie zestawy kompletne dla NP przy redukcjach AC są AC -izomorficzne.
Optymalizacja gadżetów
Jednym z zastosowań gadżetów jest udowodnienie twardości wyników aproksymacji poprzez zredukowanie problemu, o którym wiadomo, że jest trudny do przybliżenia, do innego problemu, którego twardość ma zostać udowodniona. W tej aplikacji zazwyczaj mamy rodzinę instancji pierwszego problemu, w której występuje luka w wartościach funkcji celu i w której trudno jest określić, czy dana instancja ma funkcję celu, która jest zaniżona, czy też po górnej stronie szczeliny. Redukcje użyte w tych dowodach i gadżety użyte w redukcjach muszą zachować istnienie tej luki, a siła wyniku nieprzybliżenia uzyskanego z redukcji będzie zależała od tego, jak dobrze zachowana jest luka.
Trevisana i in. (2000) sformalizowali problem znalezienia gadżetów zachowujących luki dla rodzin problemów spełniania ograniczeń , w których celem jest maksymalizacja liczby spełnionych ograniczeń. Podają jako przykład redukcję z 3-spełnialności do 2-spełnialności według Gareya, Johnsona i Stockmeyera (1976) , w której gadżet reprezentujący klauzulę 3-SAT składa się z dziesięciu klauzul 2-SAT i w którym przypisanie prawdy, które spełnia klauzulę 3-SAT spełnia również co najmniej siedem klauzul w gadżecie, podczas gdy przypisanie prawdy, które nie spełnia klauzuli 3-SAT, również nie spełnia więcej niż sześciu klauzul gadżetu. Korzystając z tego gadżetu i faktu, że (chyba że P = NP ) nie ma schematu aproksymacji w czasie wielomianowym do maksymalizacji liczby klauzul 3-SAT, które spełnia przypisanie prawdy, można pokazać, że podobnie nie ma schematu aproksymacji dla MAX 2-SOB.
Trevisana i in. pokazują, że w wielu przypadkach problemów spełniania ograniczeń, które badają, gadżety prowadzące do najsilniejszych możliwych wyników nieprzybliżalności mogą być konstruowane automatycznie, jako rozwiązanie problemu programowania liniowego . Te same redukcje oparte na gadżetach można również zastosować w innym kierunku, aby przenieść algorytmy aproksymacyjne z łatwiejszych problemów do trudniejszych. Na przykład Trevisan i in. zapewnienie optymalnego gadżetu do redukcji 3-SAT do ważonego wariantu 2-SAT (składającego się z siedmiu ważonych klauzul 2-SAT), który jest silniejszy niż ten autorstwa Gareya, Johnsona i Stockmeyera (1976) ; używając go, wraz ze znanymi programowania półokreślonego dla MAX 2-SAT, zapewniają algorytm aproksymacji dla MAX 3-SAT ze współczynnikiem aproksymacji 0,801, lepszym niż wcześniej znane algorytmy.