To pytanie może nie mieć charakteru technicznego. Jako nie-native speaker i TA dla klasy algorytmów zawsze zastanawiałem się, co oznacza gadżet w „gadżet klauzulowy” lub „gadżet zmienny”. Słownik mówi, że gadżet jest maszyną lub urządzeniem, ale nie jestem pewien, co to kolokwialne znaczenie ma w kontekście dowodu NP-zupełnego.
cc.complexity-theory
np-hardness
terminology
reductions
Federico Magallanez
źródło
źródło
Odpowiedzi:
„Gadżet” to małe wyspecjalizowane urządzenie do określonego zadania. W dowodach twardości NP, gdy redukuje się z problemu A do problemu B, potoczny termin „gadżet” odnosi się do małych (częściowych) przypadków problemu B, które są używane do „symulacji” niektórych obiektów w problemie A. zmniejszając 3SAT do 3-COLORING, gadżety klauzul są małymi wykresami, które służą do reprezentowania klauzul oryginalnej formuły, a gadżety zmiennych są małymi wykresami, które służą do reprezentowania zmiennych oryginalnej formuły. Aby upewnić się, że zmniejszenie jest prawidłowe, gadżety muszą być wykresami, które mogą być trójkolorowe w bardzo specyficzny sposób. Dlatego uważamy te małe wykresy za urządzenia, które wykonują wyspecjalizowane zadania.
W wielu przypadkach główną trudnością w udowodnieniu twardości NP jest konstruowanie odpowiednich gadżetów. Czasami te gadżety są skomplikowane i umiarkowanie duże. Proces twórczy tworzenia takich gadżetów jest czasem nazywany „gadżetowaniem”.
źródło
Formalna definicja gadżetów do redukcji optymalizacji NP pojawia się tutaj:
L. Trevisan, GB Sorkin, M. Sudan, DP Williamson. Gadżety, aproksymacja i programowanie liniowe . SIAM J. on Computing, 29 (6): 2074-2097, 2000
źródło