Oszczędna redukcja

W teorii złożoności obliczeniowej i złożoności gier oszczędna redukcja to transformacja z jednego problemu do drugiego ( redukcja ), która zachowuje liczbę rozwiązań. Nieformalnie jest to bijekcja między odpowiednimi zbiorami rozwiązań dwóch problemów. Ogólna redukcja od problemu do problemu ${\ displaystyle$$B}$ to transformacja, która gwarantuje, że zawsze, gdy rozwiązanie ${\ displaystyle A}$${\ displaystyle B}$ ma również co najmniej jedno rozwiązanie i odwrotnie. Oszczędna redukcja gwarantuje, że dla $rozwiązania$$istnieje$ unikalne rozwiązanie i .

Oszczędne redukcje są powszechnie stosowane w złożoności obliczeniowej do udowadniania trudności problemów z liczeniem , do zliczania klas złożoności, takich jak #P . Dodatkowo są one wykorzystywane w złożoności gier, jako sposób na zaprojektowanie trudnych łamigłówek, które mają unikalne rozwiązanie, czego wymaga wiele rodzajów łamigłówek.

Definicja formalna

Niech będzie przykładem problemu $\ displaystyle X$$}$ . Oszczędna redukcja z problemu $Displaystyle$ problemu $jest$ taką redukcją, że liczba rozwiązań $(x)$ równa liczbie rozwiązań problemu $)$$R$ . Jeśli taka redukcja istnieje, i jeśli mamy wyrocznię, która liczy liczbę rozwiązań $)}$$x$ , który jest instancją , wtedy możemy zaprojektować algorytm, który zlicza liczbę rozwiązań dla odpowiadającej instancji $displaystyle x$$. \displaystyle X}$ . W konsekwencji, jeśli $jest trudne, to policzenie$ liczby rozwiązań instancji $.$ rozwiązań również musi być trudne

Aplikacje

Tak jak redukcje typu „wiele jeden” są ważne dla udowodnienia NP-zupełności , tak oszczędne redukcje są ważne dla udowodnienia kompletności przy liczeniu klas złożoności , takich jak #P . Ponieważ oszczędne redukcje zachowują właściwość posiadania unikalnego rozwiązania, są one również używane w złożoności gier , aby pokazać twardość łamigłówek, takich jak sudoku , gdzie wyjątkowość rozwiązania jest ważną częścią definicji łamigłówki.

Konkretne typy oszczędnych redukcji można zdefiniować na podstawie złożoności obliczeniowej lub innych właściwości algorytmu transformacji. Na przykład oszczędna redukcja w czasie wielomianowym to taka, w której algorytm transformacji wymaga czasu wielomianowego . Są to rodzaje redukcji używane do udowodnienia #P-Completeness . W sparametryzowanej złożoności , oszczędne redukcje FPT są używane; są to oszczędne redukcje, których transformacja jest wykonalnym algorytmem o stałych parametrach i które odwzorowują ograniczone wartości parametrów na ograniczone wartości parametrów za pomocą obliczalnej funkcji.

Oszczędne redukcje w czasie wielomianowym są szczególnym przypadkiem bardziej ogólnej klasy redukcji problemów zliczania, redukcji zliczania w czasie wielomianowym .

$R(x)}$ z powszechnych technik stosowanych do udowodnienia, że ​​​​redukcja jest oszczędna $,$ jest wykazanie, że istnieje bijekcja między zbiorem rozwiązań $x$ zbiorem rozwiązań ${\ displaystyle$ , co gwarantuje, że liczba rozwiązań obu problemów jest taka sama.

Przykłady oszczędnej redukcji w dowodzeniu #P-zupełności

Klasa #P zawiera przeliczalne wersje problemów decyzyjnych NP. $o$$pod$$,$ wystąpienie problemu decyzyjnego NP pyta ${\ displaystyle x.} Poniższe$ problemu przykłady #P-kompletności opierają się na fakcie, że #SAT jest #P-kompletny.

#3SOB

To jest licząca wersja 3SAT . Można pokazać, że dowolną formułę logiczną można zapisać jako formułę w postaci 3- CNF . Każde prawidłowe przypisanie formuły boolowskiej jest prawidłowym przypisaniem odpowiedniej formuły 3-CNF i odwrotnie. Dlatego ta redukcja zachowuje liczbę satysfakcjonujących zadań i jest oszczędną redukcją. Następnie #SAT i #3SAT liczą ekwiwalenty, a #3SAT jest również #P-zupełne.

Planarny #3SAT

To jest licząca wersja Planar 3SAT. Redukcja twardości z 3SAT do Planar 3SAT podana przez Lichtensteina ma dodatkową właściwość, że dla każdego ważnego przypisania instancji 3SAT istnieje unikalne ważne przypisanie odpowiedniej instancji Planar 3SAT i odwrotnie. Stąd redukcja jest oszczędna, aw konsekwencji Planar # 3SAT jest # P-zupełny.

Cykl Hamiltona

Licząca wersja tego problemu pyta o liczbę cykli Hamiltona w danym grafie skierowanym . Seta Takahiro zapewnił redukcję tego problemu z 3SAT do tego problemu, gdy był ograniczony do wykresów skierowanych planarnie o maksymalnym stopniu 3. Redukcja zapewnia bijekcję między rozwiązaniami dla przypadku 3SAT i rozwiązaniami dla przypadku cyklu Hamiltona w płaskich grafach o maksymalnym stopniu 3. Stąd redukcja jest oszczędna, a cykl Hamiltona w planarnych grafach maksymalnego stopnia 3 skierowanych jest #P-zupełny. W związku z tym ogólna wersja problemu cyklu Hamiltona również musi być #P-zupełna.

Shakashaka

Shakashaka jest przykładem tego, jak oszczędna redukcja może być wykorzystana do pokazania twardości zagadek logicznych. Wersja decyzyjna tego problemu pyta, czy istnieje rozwiązanie danej instancji układanki. Wersja licząca pyta o liczbę różnych rozwiązań takiego problemu. Redukcja z Planar 3SAT podana przez Demaine'a, Okamoto, Ueharę i Uno zapewnia również bijekcję między zbiorem rozwiązań dla instancji Planar 3SAT a zbiorem rozwiązań dla odpowiedniej instancji Shakashaka. Stąd redukcja jest oszczędna, a licząca wersja Shakashaki jest #P-zupełna.