Czy kompletność coNP implikuje twardość NP?

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.

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 .$L_1$$L_2$$f$$x$$x \in L_1$$f(x) \in L_2$

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.$L$$M \in NP$$f$$x$$x \in M$$f(x) \in L$$L$$M$$\subseteq$$=$

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

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 ).$x \in L$$\text{M}$$x \notin \overline{L}$$\text{M}$$x$$NP$

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:$\text{NP}$$\text{coNP}$$L \in \text{coNP}$$\text{M}$

$\overline{L}$$\text{M'}$

$\text{NP}$$\text{M'}$$\text{K}$$\text{coNP}$$\text{M}$$\text{K}$$\forall$$\text{coNP}$$\text{NP}$$\text{M'}$$0$$x \in \text{K}$$\exists$$\forall$

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