Czy można wykazać twardość NP poprzez redukcje Turinga?

W artykule Złożoność problemu Frobeniusa autorstwa Ramíreza-Alfonsína okazało się, że problemem jest NP-zupełność za pomocą redukcji Turinga. Czy to jest możliwe? Jak dokładnie? Myślałem, że było to możliwe tylko w przypadku wielomianowego wielokrotnego zmniejszenia. Czy są jakieś odniesienia na ten temat?

Czy istnieją dwa różne pojęcia twardości NP, a nawet kompletności NP? Ale wtedy jestem zdezorientowany, ponieważ z praktycznego punktu widzenia, jeśli chcę wykazać, że mój problem jest trudny do przeprowadzenia w NP, którego używam?

Rozpoczęli opis w następujący sposób:

Wielomianowa redukcja Turinga z czasu do innego problemu P 2 jest algorytmem A, który rozwiązuje P 1 za pomocą hipotetycznego podprogramu A 'do rozwiązania P 2, tak że jeśli A' byłby algorytmem wielomianowym dla P 2, to A byłby algorytmem wielomianowym dla P 1 . Mówimy, że P 1 można zredukować Turinga do P 2 .$P_1$$P_2$$P_1$$P_2$$P_2$$P_1$$P_1$$P_2$

Problem nazywa się (Turing) NP-trudny, jeśli występuje problem decyzji P 2 dla NP kompletny, taki jak $P_1$$P_2$ może być zredukowana do Turinga P 1 .$P_2$$P_1$

Następnie używają takiej redukcji Turinga od problemu NP-zupełności, aby pokazać NP NP jakiegoś innego problemu.

Istnieją (przynajmniej) dwa różne pojęcia twardości NP. Zazwyczaj pojęcie, którego używa redukcji Karp, stwierdza, że język jest NP-trudne, jeśli każdy język w NP Karpa-redukuje się do L . Jeśli zmienimy redukcje Karp na redukcje Cooka, otrzymamy inne pojęcie. Każdy język, który jest karp-NP-trudny, jest również trudny do gotowania-NP, ale odwrotność jest prawdopodobnie fałszywa. Załóżmy, że NP różni się od CONP i weź swój ulubiony NP-zupełny język L . Następnie uzupełnienie $L$$L$$L$$L$ jest twardy Cook-NP, ale nie karp-NP-twardy.

Powód, dla którego jest trudny do ugotowania NP, jest następujący: weź dowolny język M w NP. Ponieważ l NP-trudne, jest funkcją polytime F tak, że x ∈ M IFF f ( x ) ∈ L IFF f ( x ) ∉ Ż l . Zmniejszenie Cooka z M do ¯ L przyjmuje x , oblicza f ( x ) , sprawdza, czy f ( x ) ∈ $\overline{L}$$M$$L$$f$$x \in M$$f(x) \in L$$f(x) \notin \overline{L}$$M$$\overline{L}$$x$$f(x)$ i wyprowadza odwrotność.$f(x) \in \overline{L}$

Powód, dla którego nie jest NP-twardy (przy założeniu, że NP różni się od coNP) jest następujący. Załóżmy, że ¯ L były twarde NP. Następnie dla każdego języka M w CONP istnieje ograniczenie polytime F tak, że x ∈ Ż M IFF f ( x ) ∈ Ż L , czyli innymi słowy, x ∈ M IFF f ( x ) ∈ l . Ponieważ L jest w NP, pokazuje to, że M jest w NP, a więc coNP $\overline{L}$$\overline{L}$$M$$f$$x \in \overline{M}$$f(x) \in \overline{L}$$x \in M$$f(x) \in L$$L$$M$$\subseteq$NP. To natychmiast implikuje, że NP coNP, a więc NP = coNP.$\subseteq$

Jeśli jakiś język Stoły NP-trudne jest P, to P = NP: dla każdego języka M w NP, użyj redukcję gotować L dać algorytmu polytime dla M . W tym sensie kompletne języki Cook-NP są również „najtrudniejsze w NP”. Z drugiej strony, to łatwo zauważyć, że kucharz-NP-trudne = Stoły CONP twardy: redukcja Gotować L mogą być konwertowane do zmniejszenia gotować ¯ L . Dlatego tracimy trochę precyzji, stosując redukcje Cooka.$L$$M$$L$$M$$L$$\overline{L}$

Prawdopodobnie istnieją inne niedociągnięcia w korzystaniu z obniżek Cooka, ale pozostawię to innym użytkownikom.

W porządku. Wielomianowa redukcja Turinga jest redukcją Cooka (jak w twierdzeniu Cooka-Levina), a redukcja problemu NP-zupełnego do nowego problemu daje twardość NP (podobnie jak redukcja wielomianowa Tiema, redukcja AKA Karp). Rzeczywiście, redukcje Karp są po prostu ograniczone Redukcje Turinga.

Różnią się (w odniesieniu do tego pytania) w wykazaniu członkostwa. Zmniejszenie Karp od problemu do problemu w NP pokazuje, że pierwszy jest w NP. Zmniejszenie gotowania w tym samym kierunku nie.