Redukcja czasu wielomianowego - Polynomial-time reduction
W teorii złożoności obliczeniowej , o ograniczenie czasu wielomian jest metodą rozwiązywania jednego problemu za pomocą drugiego. Jeden pokazuje, że jeśli istnieje hipotetyczny podprogram rozwiązujący drugi problem, to pierwszy problem można rozwiązać poprzez przekształcenie lub zredukowanie go do danych wejściowych dla drugiego problemu i wywołanie podprogramu raz lub więcej razy. Jeśli zarówno czas potrzebny do przekształcenia pierwszego problemu w drugi, jak i liczba wywołań podprogramu są wielomianowe, to pierwszy problem jest wielomianowy sprowadzalny do drugiego.
Redukcja wielomianowa dowodzi, że pierwszy problem nie jest trudniejszy niż drugi, ponieważ ilekroć istnieje wydajny algorytm dla drugiego problemu, istnieje również dla pierwszego problemu. W przeciwieństwie do tego , jeśli nie istnieje żaden wydajny algorytm dla pierwszego problemu, nie istnieje również dla drugiego problemu. Redukcje wielomianowe są często używane w teorii złożoności do definiowania zarówno klas złożoności, jak i kompletnych problemów dla tych klas.
Rodzaje obniżek
Trzy najczęstsze typy redukcji wielomianowych, od najbardziej do najmniej restrykcyjnych, to wielomianowe redukcje wiele-jeden , redukcje w oparciu o tabelę prawdy i redukcje Turinga . Najczęściej stosowanymi z nich są redukcje wiele-jeden, aw niektórych przypadkach wyrażenie „redukcja wielomianowa” może być używane w znaczeniu redukcji wielomianowej wiele-jednej. Najbardziej ogólne redukcje to redukcje Turinga, a najbardziej restrykcyjne to redukcje wielu jeden z redukcją tabeli prawdy zajmującą przestrzeń pomiędzy.
Redukcje wiele-jedne
Wielomian czasu wiele jeden redukcja z problemu A do problemu B (z których oba są zazwyczaj wymagane, aby mieć problemy decyzyjne ) to algorytm wielomianowy czasu dla przekształcenia wejść do problemu A do wejść do problemu B tak, że przekształcone problem ma taki sam wynik, jak oryginalny problem. Instancja x problemu A może zostać rozwiązana przez zastosowanie tej transformacji do utworzenia instancji y problemu B , podając y jako dane wejściowe algorytmu problemu B i zwracając jego wynik. Wielomianowe redukcje wiele jeden mogą być również znane jako przekształcenia wielomianowe lub redukcje Karpa , nazwane na cześć Richarda Karpa . Redukcja tego typu jest oznaczona przez lub .
Redukcje według tabeli prawdy
Redukcja tabeli prawdy w czasie wielomianowym z problemu A do problemu B (oba problemy decyzyjne) jest algorytmem czasu wielomianowego do przekształcania danych wejściowych do problemu A w ustaloną liczbę danych wejściowych do problemu B , tak że dane wyjściowe dla oryginalnego problemu można wyrazić jako funkcję wyjść dla B . Funkcja odwzorowująca dane wyjściowe dla B na dane wyjściowe dla A musi być taka sama dla wszystkich danych wejściowych, aby można ją było wyrazić za pomocą tabeli prawdy . Redukcja tego typu może być oznaczona wyrażeniem .
Redukcje Turinga
Wielomianowa redukcja Turinga z problemu A do problemu B jest algorytmem, który rozwiązuje problem A za pomocą wielomianowej liczby wywołań podprogramu dla problemu B i czasu wielomianowego poza tymi wywołaniami podprogramu. Wielomianowe redukcje Turinga są również znane jako redukcje Cooka , nazwane na cześć Stephena Cooka . Redukcja tego typu może być oznaczona wyrażeniem . Redukcje wiele-jeden można traktować jako ograniczone warianty redukcji Turinga, w których liczba wywołań podprogramu dla problemu B jest dokładnie jedna, a wartość zwracana przez redukcję jest taka sama, jak zwracana przez podprogram.
Kompletność
Kompletny problemem dla danego złożoności klasy C i redukcji ≤ jest problemem P , który należy do C , tak, że każdy problem w C ma redukcję ≤ P . Na przykład, problem jest NP -Complete jeśli należy do NP i wszystkie problemy NP mieć wielomian czasie wiele -on redukcje do niego. Problem należący do NP można udowodnić jako NP-zupełny , znajdując do niego pojedynczą wielomianową redukcję wiele-jeden ze znanego problemu NP- zupełnego. Wielomian czasu wiele-jeden redukcje zostały wykorzystane do określenia kompletnych problemy dla innych klas złożoności, w tym PSPACE -Complete językach i EXPTIME -Complete językach.
Każdy problem decyzyjny w P (klasie wielomianowych problemów decyzyjnych) można zredukować do każdego innego nietrywialnego problemu decyzyjnego (gdzie nietrywialny oznacza, że nie każde dane wejściowe mają taki sam wynik) przez wielomianową redukcję. Aby przekształcić wystąpienie problemu A w B , rozwiąż A w czasie wielomianowym, a następnie użyj rozwiązania, aby wybrać jeden z dwóch wystąpień problemu B z różnymi odpowiedziami. Dlatego w przypadku klas złożoności w obrębie P, takich jak L , NL , NC i samego P , wielomianowych redukcji nie można użyć do zdefiniowania kompletnych języków: gdyby były używane w ten sposób, każdy nietrywialny problem w P byłby kompletny. Zamiast tego, słabsze redukcje, takie jak redukcje w przestrzeni logarytmicznej lub redukcje NC, są używane do definiowania klas kompletnych problemów dla tych klas, takich jak problemy P- zupełne .
Definiowanie klas złożoności
Definicje klas złożoności NP , PSPACE i EXPTIME nie obejmują redukcji: redukcje wchodzą do ich badań tylko w definicji kompletnych języków dla tych klas. Jednak w niektórych przypadkach klasę złożoności można zdefiniować przez redukcje. Jeśli C jest jakimkolwiek problemem decyzyjnym , to można zdefiniować klasę złożoności C składającą się z języków A dla których . W takim przypadku C będzie automatycznie kompletne dla C , ale C może mieć również inne kompletne problemy.
Przykładem tego jest klasa złożoności zdefiniowana na podstawie egzystencjalnej teorii rzeczywistości , problem obliczeniowy, o którym wiadomo, że jest NP- trudny i w PSPACE , ale nie jest kompletny dla NP , PSPACE lub dowolnego języka w wielomianu hierarchia . jest zbiorem problemów podlegających redukcji wielomianowej wiele-jeden do egzystencjalnej teorii rzeczywistości; to ma kilka innych problemów, takich jak kompletne ustalenia prostoliniowy numer przejście danego undirected wykresu . Każdy problem w dziedziczy własność przynależności do PSPACE , a każdy -zupełny problem jest NP -trudny.
Podobnie klasa złożoności GI składa się z problemów, które można sprowadzić do problemu izomorfizmu grafu . Ponieważ wiadomo, że izomorfizm grafów należy zarówno do NP, jak i co- AM , to samo dotyczy każdego problemu w tej klasie. Problemem jest GI -kompletne, jeśli jest kompletne dla tej klasy; sam problem izomorfizmu grafu jest GI -kompletny, podobnie jak kilka innych powiązanych problemów.