Czy kompletność coNP implikuje twardość NP?

12

Czy kompletność coNP implikuje twardość NP? W szczególności mam problem, który wykazałem, że jest kompletny coNP. Czy mogę twierdzić, że jest to trudne NP? Zdaję sobie sprawę, że mogę żądać twardości coNP, ale nie jestem pewien, czy ta terminologia jest standardowa.

Nie mam nic przeciwko twierdzeniu, że jeśli problem NP-zupełny należał do coNP, to NP = coNP. Jednak te notatki z wykładu stwierdzają, że jeśli trudny problem NP należy do coNP, to NP = coNP. Sugerowałoby to, że nie mogę twierdzić, że mój problem jest trudny do NP (lub że udowodniłem, że coNP = NP, co bardzo wątpię).

Być może coś jest nie tak z moim myśleniem. Uważam, że kompletny problem z koNP jest trudny do NP, ponieważ:

  1. każdy problem w NP można zredukować do jego uzupełnienia, które będzie należeć do coNP.
  2. problem uzupełnienia w coNP sprowadza się do mojego problemu pełnego coNP.
  3. dlatego mamy redukcję z każdego problemu w NP do mojego coNP-zupełnego, więc mój problem jest NP-trudny.
Austin Buchanan
źródło
jednym słowem nie! przynajmniej w oparciu o aktualną wiedzę. pytanie jest ściśle związane z P =? NP (lub ściślej coNP =? NP, który jest również otwarty). należy zauważyć, że jeśli udowodniono, że coNP ≠ NP, to P ≠ NP jest również udowodnione, ponieważ P jest zamknięte z dopełniaczem.
vzn

Odpowiedzi:

10

Twierdzisz, że każdy problem w NP można zredukować do jego uzupełnienia , i dotyczy to redukcji Turinga, ale (prawdopodobnie) nie w przypadku redukcji wielokrotnych. Wielokrotna redukcja od do L 2 jest funkcją czasu policy f, taką, że dla wszystkich x , x L 1 iff f ( x ) L 2 .L1L2fxxL1f(x)L2

Jeżeli jakiś problem w CONP były NP-trudny, to dla każdego języka M N P byłoby funkcję polytime C tak, że dla wszystkich x , x M IFF f ( x ) l . Ponieważ L znajduje się w coNP, daje to algorytm coNP dla M , pokazując, że NP coNP, a więc NP = coNP. Większość badaczy nie spodziewa się, że tak się stanie, więc problemy w koNP prawdopodobnie nie są trudne NP.LMNPfxxMf(x)LLM=

Powodem, dla którego używamy redukcji Karp zamiast redukcji Turinga, jest to, że możemy rozróżnić problemy trudne do NP i trudne do CoNP. Zobacz tę odpowiedź, aby uzyskać więcej informacji (redukcje Turinga nazywane są redukcjami Cooka w tej odpowiedzi).

Wreszcie, coNP-hard i coNP-complete są standardową terminologią i możesz z nich korzystać.

Yuval Filmus
źródło
„ale nie w przypadku redukcji jeden na jeden” - czy nie ma problemu z decyzją dokładnie, że nie wiemy, czy istnieją redukcje Karp z ( ko ) języka NP do jego dopełnienia? NP=?koNPwspółNP
G. Bach,
Zgadza się i to też pokazuję w odpowiedzi. Kiedy stwierdziłem, że nie jest to prawdą w przypadku redukcji wielokrotnych jeden, nie miałem na myśli tego w logicznym sensie, ale raczej w tym sensie, że „redukcja, o której myślisz, jest redukcją Turinga, ale nie redukcją wielokrotną jeden” .
Yuval Filmus
Och w porządku, tak, to prawdopodobnie problem.
G. Bach,
Dzięki. Co jest na to dobrym przykładem? W szczególności w przypadku „NP = coNP w ramach obniżek Cooka, ale uważa się, że różnią się one w stosunku do redukcji Karp”?
Austin Buchanan,
Przekonanie, że NP różni się od coNP, jest dość powszechne. Czasami przypisuje się to Stephenowi Cookowi. Ta twardość NP jest taka sama jak twardość coNP w ramach obniżek Cooka wynika bezpośrednio z definicji.
Yuval Filmus,
6

Problem z tym rozumowaniem jest pierwszym krokiem. W przypadku deterministycznym możesz zdecydować za pomocą TM M iff możesz zdecydować x ¯ L za jego pomocą, ponieważ sposobem na to jest po prostu odwrócenie bitu wyjściowego M, ponieważ jego wyjście zależy tylko od x (jeśli porównaj z definicją weryfikatora N P ).xL.M.xL.¯M.xN.P.

W przypadku niedeterministycznych stosując definicję weryfikatora, to nie wiadomo, czy można zbudować -verifier z CONP -verifier lub odwrotnie, a problemem jest to, że mają one różne kwantyfikatorów w definicjach, że weryfikator maszyn muszą spełniać. Niech L coNP , wtedy mamy weryfikator DTM M taki, że:NPkoNPL.koNPM.

xL.z{0,1}p(|x|):M.(x,z)=1

L.¯M

xL.¯z{0,1}q(|x|):M(x,z)=1

NPMK.koNPM.K.koNPNPM0xK.

Być może bardziej abstrakcyjnie: nie jest jasne, jak zbudować (w czasie wielomianowym) maszynę, która rozpoznaje dokładnie elementy języka, bez względu na to, jaki certyfikat z nimi pochodzi, z maszyny, która rozpoznaje dokładnie elementy języka, które mają jakiś certyfikat dla ale dla których również niektóre certyfikaty nie działają.

G. Bach
źródło
4
Nieoczekiwanie wiadomo jednak, że NL = coNL, NPSPACE = coNPSPACE i ogólnie niedeterministyczne klasy zdefiniowane przez ograniczenia przestrzenne są zamykane przy uzupełnieniu. To jest twierdzenie Immermana-Szelepcsényi.
Yuval Filmus
Co ciekawe, nie wiedziałem o tym - ale intuicja, która za tym stoi, prawdopodobnie jest taka, jak zawsze w przypadku klas kosmicznych: możemy po prostu ponownie wykorzystać przestrzeń.
G. Bach,
stlognst