Czy możemy skonstruować redukcję Karp z redukcji Cooka między problemami NP?

Mieliśmy kilka pytań na temat relacji redukcji Cooka i Karp . Oczywiste jest, że redukcje Cooka (redukcje Turinga w czasie wielomianowym) nie definiują tego samego pojęcia kompletności NP jak redukcje Karp (redukcje w postaci wielomianu w jednym czasie), które są zwykle stosowane. W szczególności redukcje Cooka nie mogą oddzielić NP od co-NP, nawet jeśli P NP. Dlatego nie powinniśmy używać obniżek Cooka w typowych dowodach redukcji.$\neq$

Teraz uczniowie znaleźli recenzowaną pracę [1], która wykorzystuje redukcję Cooka do wykazania, że ​​problem jest trudny do uniknięcia. Nie dałem im pełnej oceny za obniżkę, którą wzięli stamtąd, ale zastanawiam się.

Od redukcje Cooka zrobić zdefiniować pojęcie podobną twardość redukcji Karp, czuję, że powinien być w stanie oddzielić P z NPC wzgl. co-NPC, przy założeniu P NP. W szczególności (coś podobnego) powinny być spełnione następujące warunki:$\neq$

$\qquad\displaystyle L_1 \in \mathrm{NP}, L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1 \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ .

Ważnym samorodkiem jest to, że więc wspomniana powyżej niewrażliwość jest obchodzona. Teraz „wiemy” - z definicji NPC - że .$L_1 \in \mathrm{NP}$$L_2 \leq_{\mathrm{Karp}} L_1$

Jak zauważył Vor , nie jest to takie łatwe (z uwzględnieniem zapisu):

Załóżmy, że , a następnie z definicji dla wszystkich języków mamy mieć ; a jeśli powyższa implikacja jest prawdziwa, to a zatem które wciąż jest pytaniem otwartym.$L_1 \in \mathrm{NPC}_{\mathrm{Cook}}$$L_2 \in \mathrm{NPC}_{\mathrm{Karp}} \subseteq \mathrm{NP}$$L_2 \leq_{\mathrm{Cook}} L_1$$L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$$\mathrm{NPC}_{\mathrm{Karp}} = \mathrm{NPC}_{\mathrm{Cook}}$

Mogą istnieć inne różnice między dwoma NPC, ale co-NP.

W przeciwnym razie, czy istnieją jakieś znane (nietrywialne) kryteria, dla których zmniejszenie Cooka oznacza twardość Karp-NP, tj. Czy znamy predykaty z$P$

$\qquad\displaystyle L_2 \in \mathrm{NPC}_{\mathrm{Karp}}, L_2 \leq_{\mathrm{Cook}} L_1, P(L_1,L_2) \implies L_1 \in \mathrm{NPC}_{\mathrm{Karp}}$ ?

1. O złożoności wyrównywania wielu sekwencji przez L. Wanga i T. Jianga (1994)

jest to ogólnie otwarty problem TCS podlegający ciągłym badaniom, czy i dokładne warunki Redukcje Cooka i Karp są równoważne i najwyraźniej są ściśle związane z otwartym pytaniem NP =? coNP i innymi separacjami klas złożoności, np. E =? NE (wrt rzadkie języki).

oto dwa artykuły badawcze na ten temat i dalsze informacje na tcs.se poprzez podobne pytanie:

• Czy Cook i Karp są zawsze tacy sami? Beigel, Fortnow

• Cook vs. Karp-Levin: Rozdzielanie pojęć kompletności, jeśli NP nie jest mały (1995) Lutz, Mayordomo

• wiele redukcji jeden w porównaniu z redukcjami Turinga, aby zdefiniować NPC , tcs.se

Ogólnie rzecz biorąc, aby mechanicznie przekształcić problem z gotowaniem w problem z karpiem, musi istnieć coś specjalnego z samym językiem.

Na przykład nawet bardzo ograniczona wersja redukcji Cooka, a mianowicie redukcja ujemna (redukuj do jednego przypadku, tak jak robi to Karp, pytaj o odpowiedź, a następnie neguj), wymagałaby czegoś specjalnego w języku aby łatwo zmienić ją w standardową redukcję Karp.$L$

Możemy powiedzieć, że jeśli ma następującą właściwość :$L$

W dowolnym przypadku możemy w czasie wielomianowym wygenerować , tak że .$x$$x'=f(x)$$L(x)\neq L(x')$

Możemy więc uzyskać standardową redukcję Karp, najpierw zmniejszając do przez redukcję ujemną, a następnie wytwarzając .$g(x)$$f(g(x))$

Jak widać, właściwości te zwykle nie są widoczne w teorii złożoności, teorii obliczalności. Podsumowując, jest mało prawdopodobne, aby zmienić Cooka w Karp.