Co oznacza „gadżet” w redukcji twardej NP?

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.

„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”.

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