Wielokrotne redukcje vs. redukcje Turinga w celu zdefiniowania NPC

Dlaczego większość ludzi woli stosować redukcje wielokrotne jeden do zdefiniowania kompletności NP zamiast, na przykład, redukcji Turinga?

Dwa powody:

(1) tylko kwestia minimalności: bycie NPC pod wieloma redukcjami jest formalnie silniejszym stwierdzeniem, a jeśli otrzymujesz silniejsze oświadczenie (tak jak Karp i jak prawie zawsze), to dlaczego nie powiedzieć tak?

(2) Mówienie o redukcjach wielokrotnych jeden prowadzi do bogatszej, delikatniejszej hierarchii. Na przykład rozróżnienie NP i co-NP znika w ramach redukcji Turinga.

Jest to podobne w duchu do tego, dlaczego często stosuje się redukcje przestrzeni logicznej, a nie ograniczenia czasu.

Nie wiem, czy istnieje preferencja, ale przypuszcza się, że są to odrębne pojęcia. Oznacza to, że redukowalność Turinga jest przypuszczalna jako silniejsze pojęcie. (Istnieją A i B takie, że A jest T-redukowalne do B, ale nie moe redukowalne do B.) Jedna praca, która omawia to jest ta autorstwa Lutza i Mayordomo. Proponują wzmocnienie zdania P! = NP; z grubsza, ta NP obejmuje niemającą znaczenia DODATEK. To założenie pozwala im wykazać, że dwa pojęcia redukowalności są odrębne.

Myślę, że powodem, dla którego ludzie wolą (na początek) redukcje wielokrotne, jest pedagogiczna - redukcja wielokrotności z A do B jest w rzeczywistości funkcją strun, podczas gdy redukcja Turinga wymaga wprowadzenia wyroczni.

Zauważ, że redukcja Cooka (wielomianowy czas Turinga) i redukcja Karp-Levina (wielomianowy czas wielomianowy) są znane bezwzględnie w E bezwzględnie, według Ko i Moore'a, i osobno przez Watanabe (jak wspomniano w pracy Lutza i Mayordomo) w odpowiedzi Aarona Sterlinga).

Redukcje Turinga są pod tym względem silniejsze niż redukcje mapowania jeden na jeden: Redukcje Turinga umożliwiają mapowanie języka na jego dopełnienie. W rezultacie może niejasno różnicować (na przykład) NP i coNP. W oryginalnym artykule Cooka nie spojrzał na to rozróżnienie (iirc Cook faktycznie użył formuł DNF zamiast CNF), ale prawdopodobnie szybko stało się jasne, że była to ważna separacja, a wielokrotne redukcje ułatwiły sobie z tym poradzić .

aby skoczyć nieco pod innym kątem / odpowiedź tutaj przez AS, to jest otwarte pytanie (także tutaj ) na granicach TCS, czy redukcje Cooka („Turinga”) są inne niż redukcje Karp-Levina („wiele-jeden”), być może równoważne (głównym? kluczowi?) otwartym pytaniom o podziały klas złożoności. oto nowy wynik w tym kierunku

Oddzielanie kompletności kucharskiej od kompletności Karp-Levina pod hipotezą / najgorszym przypadkiem twardości Mandala, A. Pavana, Rajeswari Venugopalan (ECCC TR14-126)

Pokazujemy, że istnieje język, w którym Turing jest kompletny dla NP, ale nie wiele - jeden kompletny dla NP, w najgorszym przypadku hipoteza twardości.

Definicje skutecznej redukowalności są częściowo motywowane analogią z teorią rekurencji. W teorii rekurencji redukcje m są ściśle powiązane z hierarchią arytmetyczną. (m-redukcje zachowują stopień arytmetyczny). Klasyfikacje arytmetyczne są ważne poza zwykłymi obliczeniami. Na przykład można powiedzieć, że prawdziwe twierdzenia są możliwe do udowodnienia w Robinsona .$\Sigma_1$$Q$

W teorii złożoności istnieje również pojęcie „hierarchii wielomianowej”, chociaż w przeciwieństwie do hierarchii arytmetycznej można przypuszczać, że istnieje. Prowadzi to do subtelniejszych klasyfikacji niż „Czy ten problem jest tak trudny do rozwiązania jak NP?”

Ogólnie rzecz biorąc, redukcja wielu (Karp) jest łatwiejsza do zaprojektowania, ponieważ jest ograniczoną formą redukcji, która wykonuje jedno wywołanie, a głównym zadaniem jest przekształcenie danych wejściowych na inne kodowanie. Redukcja Turinga może wiązać się ze złożoną logiką. Istnienie zestawu, który jest kompletny dla NP w ramach redukcji Turinga, ale nie w przypadku redukcji wielokrotnej jeden, oznacza, że ​​P! = NP.

Na przykład, niezadowalanie jest całkowite dla NP przy redukcji Cooka, ale nie wiadomo, że jest kompletne dla NP przy redukcji Karp. Więc jeśli udowodnisz, że nie ma redukcji Karp z SAT do UNSAT (równoważnie z UNSAT do SAT), to udowodnisz, że NP! = CoNP, a zatem P! = NP.