Redukcja (złożoność) - Reduction (complexity)

Przykład redukcji z problemu spełnialności logicznej ( AB ) ∧ ( ¬ A ∨ ¬ B ∨ ¬ C ) ∧ ( ¬ ABC ) do problemu pokrycia wierzchołków . Niebieskie wierzchołki tworzą minimalne pokrycie wierzchołków, a niebieskie wierzchołki w szarym owalu odpowiadają satysfakcjonującemu przypisaniu prawdziwości oryginalnej formuły.

W teorii obliczalności i teorii złożoności obliczeniowej , o ograniczenie jest algorytm przekształcania jednego problemu na inny problem. Wystarczająco skuteczna redukcja jednego problemu do drugiego może być wykorzystana do wykazania, że ​​drugi problem jest co najmniej tak samo trudny jak pierwszy.

Intuicyjnie problem A można zredukować do problemu B , jeśli algorytm do efektywnego rozwiązania problemu B (jeśli istniał) mógłby być również użyty jako podprogram do efektywnego rozwiązania problemu A. Kiedy to prawda, rozwiązanie A nie może być trudniejsze niż rozwiązanie B . „Trudniejsze” oznacza posiadanie wyższego oszacowania wymaganych zasobów obliczeniowych w danym kontekście (np. wyższa złożoność czasowa , większe wymagania dotyczące pamięci, kosztowna potrzeba dodatkowych rdzeni procesora sprzętowego dla rozwiązania równoległego w porównaniu z rozwiązaniem jednowątkowym itp.) . Istnienie redukcji od A do B można zapisać w notacji skróconej Am B , zwykle z indeksem na ≤ w celu wskazania typu zastosowanej redukcji (m : redukcja odwzorowania , p : redukcja wielomianowa ).

Struktura matematyczna generowana na zbiorze problemów przez redukcje określonego typu generalnie tworzy preorder , którego klasy równoważności mogą być użyte do określenia stopni nierozwiązywalności i klas złożoności .

Wstęp

Istnieją dwie główne sytuacje, w których musimy zastosować redukcje:

  • Po pierwsze, próbujemy rozwiązać problem, który jest podobny do problemu, który już rozwiązaliśmy. W takich przypadkach często szybkim sposobem rozwiązania nowego problemu jest przekształcenie każdego wystąpienia nowego problemu w przypadki starego problemu, rozwiązanie ich przy użyciu naszego istniejącego rozwiązania, a następnie wykorzystanie ich do uzyskania ostatecznego rozwiązania. To chyba najbardziej oczywiste zastosowanie redukcji.
  • Po drugie: załóżmy, że mamy problem, który, jak udowodniliśmy, jest trudny do rozwiązania i mamy podobny nowy problem. Możemy podejrzewać, że jest to również trudne do rozwiązania. Argumentujemy przez sprzeczność: załóżmy, że nowy problem jest łatwy do rozwiązania. Wtedy, jeśli możemy pokazać, że każdy przypadek starego problemu można łatwo rozwiązać, przekształcając go w przypadki nowego problemu i rozwiązując je, mamy sprzeczność. To udowadnia, że ​​nowy problem jest również trudny.

Bardzo prostym przykładem redukcji jest mnożenie do kwadratu . Załóżmy, że wszystko, co wiemy, to dodawać, odejmować, brać kwadraty i dzielić przez dwa. Możemy wykorzystać tę wiedzę w połączeniu z następującym wzorem, aby otrzymać iloczyn dowolnych dwóch liczb:

Mamy też redukcję w innym kierunku; oczywiście, jeśli możemy pomnożyć dwie liczby, możemy liczbę podbić do kwadratu. Wydaje się to sugerować, że te dwa problemy są równie trudne. Ten rodzaj redukcji odpowiada redukcji Turinga .

Redukcja staje się jednak znacznie trudniejsza, jeśli dodamy ograniczenie, że z funkcji do kwadratu możemy skorzystać tylko raz i tylko na końcu. W tym przypadku, nawet jeśli wolno nam używać wszystkich podstawowych operacji arytmetycznych, w tym mnożenia, w ogóle nie istnieje redukcja, ponieważ aby uzyskać pożądany wynik jako kwadrat, musimy najpierw obliczyć jego pierwiastek kwadratowy, a ten kwadrat pierwiastek może być liczbą niewymierną, taką jak ta, której nie można skonstruować za pomocą operacji arytmetycznych na liczbach wymiernych. Idąc w drugą stronę, z pewnością możemy jednak podbić liczbę do kwadratu za pomocą tylko jednego mnożenia, tylko na końcu. Korzystając z tej ograniczonej formy redukcji, pokazaliśmy, że nie jest zaskakujący wynik, że mnożenie jest ogólnie trudniejsze niż podnoszenie do kwadratu. Odpowiada to redukcji wiele-jeden .

Nieruchomości

Redukcja jest preordering , który jest zwrotny i przechodni na P ( N ) x P ( n ), gdzie P ( N ) jest zespół zasilający z liczb naturalnych .

Rodzaje i zastosowania redukcji

Jak opisano w powyższym przykładzie, istnieją dwa główne typy redukcji stosowanych w złożoności obliczeniowej, redukcja wielu jeden i redukcja Turinga . Redukcje „wielo-jedne” odwzorowują przypadki jednego problemu na przypadki innego; Redukcje Turinga obliczają rozwiązanie jednego problemu, zakładając, że drugi problem jest łatwy do rozwiązania. Redukcja wiele-jeden jest silniejszym typem redukcji Turinga i jest bardziej skuteczna w rozdzielaniu problemów na odrębne klasy złożoności. Jednak zwiększone ograniczenia dotyczące obniżek typu „wiele jeden” sprawiają, że trudniej je znaleźć.

Problem jest kompletny dla klasy złożoności, jeśli każdy problem w klasie sprowadza się do tego problemu, a także znajduje się w samej klasie. W tym sensie problem reprezentuje klasę, ponieważ każde jego rozwiązanie, w połączeniu z redukcjami, może być użyte do rozwiązania każdego problemu w klasie.

Aby jednak były użyteczne, redukcje muszą być łatwe . Na przykład, całkiem możliwe jest zredukowanie trudnego do rozwiązania problemu NP-zupełnego, takiego jak problem spełnialności logicznej, do problemu trywialnego, takiego jak ustalenie, czy liczba jest równa zero, przez maszynę redukcyjną, która rozwiązuje problem w czasie wykładniczym i na wyjściu zero tylko jeśli istnieje rozwiązanie. Nie daje to jednak wiele, bo chociaż możemy rozwiązać nowy problem, to przeprowadzenie redukcji jest tak samo trudne, jak rozwiązanie starego. Podobnie, obliczanie redukujące funkcji nieobliczalnej może zredukować problem nierozstrzygalny do rozstrzygalnego. Jak zauważa Michael Sipser we Wstępie do Teorii Obliczeń : „Redukcja musi być łatwa, w stosunku do złożoności typowych problemów w klasie […] Jeśli sama redukcja byłaby trudna do obliczenia, łatwe rozwiązanie kompletnego problem niekoniecznie przyniesie łatwe rozwiązanie problemów sprowadzających się do niego.”

Dlatego właściwe pojęcie redukcji zależy od badanej klasy złożoności. Podczas badania klasy złożoności NP i trudniejszych klas, takich jak hierarchia wielomianowa , stosuje się redukcje wielomianowe w czasie . Podczas studiowania klas w ramach P, takich jak NC i NL , stosuje się redukcję przestrzeni logarytmicznej . W teorii obliczalności stosuje się również redukcje, aby pokazać, czy problemy są w ogóle rozwiązywane przez maszyny; w tym przypadku redukcje są ograniczone tylko do funkcji obliczalnych .

W przypadku problemów z optymalizacją (maksymalizacją lub minimalizacją) często myślimy w kategoriach redukcji z zachowaniem przybliżenia . Załóżmy, że mamy dwa problemy optymalizacyjne, takie, że przypadki jednego problemu można odwzorować na przypadki drugiego w taki sposób, że prawie optymalne rozwiązania wystąpień drugiego problemu mogą zostać przekształcone z powrotem, aby uzyskać prawie optymalne rozwiązania pierwszego. W ten sposób, jeśli mamy algorytm optymalizacji (lub algorytm aproksymacyjny ), który znajduje prawie optymalne (lub optymalne) rozwiązania dla instancji problemu B, oraz skuteczną redukcję z zachowaniem przybliżenia od problemu A do problemu B, przez złożenie otrzymujemy optymalizację algorytm, który daje prawie optymalne rozwiązania przypadków problemu A. Redukcje zachowujące przybliżenie są często używane do udowodnienia twardości wyników aproksymacji : jeśli jakiś problem optymalizacji A jest trudny do aproksymacji (przy pewnym założeniu złożoności) w ramach współczynnika lepszego niż α dla niektórych α i istnieje redukcja z zachowaniem przybliżenia β od problemu A do problemu B, możemy stwierdzić, że problem B jest trudny do aproksymacji we współczynniku α/β.

Przykłady

Szczegółowy przykład

Poniższy przykład pokazuje, jak wykorzystać redukcję z problemu zatrzymania, aby udowodnić, że język jest nierozstrzygalny. Załóżmy, że H ( M , w ) jest problemem ustalenia, czy dana maszyna Turinga M zatrzymuje się (poprzez akceptację lub odrzucenie) na łańcuchu wejściowym w . Wiadomo, że ten język jest nierozstrzygalny. Załóżmy, że E ( M ) jest problemem ustalenia, czy język, który akceptuje dana maszyna Turinga M, jest pusty (innymi słowy, czy M w ogóle akceptuje jakieś łańcuchy). Pokazujemy, że E jest nierozstrzygalne przez redukcję z H .

Aby uzyskać sprzeczność, załóżmy, że R jest decydentem dla E . Wykorzystamy to do stworzenia decydenta S dla H (o którym wiemy, że nie istnieje). Mając dane wejściowe M i w (maszyna Turinga i jakiś ciąg wejściowy), zdefiniuj S ( M , w ) z następującym zachowaniem: S tworzy maszynę Turinga N, która akceptuje tylko wtedy, gdy ciąg wejściowy do N to w, a M zatrzymuje się na wejściu w i nie zatrzymuje się inaczej. Decydent S może teraz ocenić R ( N ), aby sprawdzić, czy język akceptowany przez N jest pusty. Jeśli R akceptuje N , to język akceptowany przez N jest pusty, więc w szczególności M nie zatrzymuje się na wejściu w , więc S może odrzucić. Jeśli R odrzuca N , to język akceptowany przez N jest niepusty, więc M zatrzymuje się na wejściu w , więc S może zaakceptować. Zatem, gdybyśmy mieli decydent R dla E , bylibyśmy w stanie stworzyć decydent S dla problemu zatrzymania H ( M , w ) dla dowolnej maszyny M i wejścia w . Ponieważ wiemy, że takie S nie może istnieć, wynika z tego, że język E jest również nierozstrzygalny.

Zobacz też

Bibliografia

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest i Clifford Stein, Wprowadzenie do algorytmów , MIT Press, 2001, ISBN  978-0-262-03293-3
  • Hartley Rogers, Jr.: Teoria funkcji rekurencyjnych i efektywnej obliczalności , McGraw-Hill, 1967, ISBN  978-0-262-68052-3 .
  • Peter Bürgisser: Kompletność i redukcja w teorii złożoności algebraicznej , Springer, 2000, ISBN  978-3-540-66752-0 .
  • ER Griffor: Podręcznik teorii obliczalności , North Holland, 1999, ISBN  978-0-444-89882-1 .