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

19

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 .P1P2P1P2P2P1P1P2

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

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

użytkownik2145167
źródło

Odpowiedzi:

17

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 LLLLL 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 ) ¯L¯M.LfxMf(x)Lf(x)L¯ML¯xf(x) i wyprowadza odwrotność.f(x)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 L¯L¯MfxM¯f(x)L¯xMf(x)LLMNP. To natychmiast implikuje, że NP coNP, a więc NP = coNP.

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.LMLMLL¯

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

Yuval Filmus
źródło
Nie do końca zrozumiałem to wszystko, co muszę powiedzieć. Ale mam inne pytanie, może możesz na to odpowiedzieć (ponieważ nie ma tak wielu innych odpowiedzi): co, jeśli mam czerwony Turinga. od NP-kompletnego problemu A do jakiegoś problemu B i czerwonego karpia. od problemu B do problemu C. Czy to określa kompletność NP problemu C (członkostwo nie stanowi problemu)? I ogólnie, czy mogę nazwać problem B NP-trudny, czy raczej (Turing) NP-trudny? Dzięki!
user2145167 10.04.13
4
Dwie redukcje Karp składają się na redukcję Karp, a dwie redukcje Cooka składają się na redukcję Cooka. Ponieważ redukcja Karp jest również redukcją Cooka, jeśli skomponujesz redukcję Karp i redukcję Cooka, otrzymasz redukcję Cooka. Ale generalnie nie dostajesz redukcji Karp.
Yuval Filmus
@YuvalFilmus, czy mógłbyś wyjaśnić, co chciałeś rozumieć przez iff f ( x ) L iff f ( x ) ¯ L ? xMf(x)Lf(x)L¯
Omar Shehab,
Karp redukcji od do L jest funkcją f (polytime w tym przypadku) w taki sposób, że x M IFF f ( x ) l . Dla każdego f , x zawsze utrzymuje, że f ( x ) L iff f ( x ) ¯ L , gdzie ¯ L jest uzupełnieniem L (w odniesieniu do zakresu f ). MLfxMf(x)L f,xf(x)Lf(x)L¯L¯Lf
Yuval Filmus
6

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.

Luke Mathieson
źródło
Dzięki. Nawet nie zdawałem sobie sprawy, że jeden pokazuje członkostwo, używając jawnie redukcji Karp. Ale to ma sens. Ale można pokazać członkostwo NP, stosując redukcje Turinga w obu kierunkach, prawda?
user2145167
1
@ user2145167 nie, odpowiedź Yuvala podaje pełną historię tutaj, ale w skrócie, redukcje Cooka są słabsze, więc wpuszczaj więcej - np. możesz przejść od dowolnego problemu współ-NP poprzez redukcję Cooka do dowolnego problemu NP-zupełnego, który nie jest prawdziwe dla redukcji karp.
Luke Mathieson