co-NP - co-NP
W teorii złożoności obliczeniowej , co-NP jest klasa złożoności . Problem decyzyjny X jest członkiem współpracy NP wtedy i tylko wtedy, gdy jego dopełnienie X jest w klasie złożoności NP . Klasę można zdefiniować w następujący sposób: problem decyzyjny występuje w ko-NP dokładnie wtedy, gdy tylko żadne -instancje nie mają „ certyfikatu ” o długości wielomianowej i istnieje algorytm wielomianowy, który można wykorzystać do weryfikacji dowolnego rzekomego certyfikatu.
Oznacza to, że co-NP jest zbiorem problemów decyzyjnych, w których istnieje wielomian p(n) i ograniczona w czasie wielomianem maszyna Turinga M takie, że dla każdego przypadku x , x jest brakiem instancji wtedy i tylko wtedy, gdy: dla niektórych możliwy certyfikat c o długości ograniczonej przez p(n) , maszyna Turinga M akceptuje parę ( x , c ).
Problemy komplementarne
Podczas gdy problem NP pyta, czy dana instancja jest instancją typu tak , jego uzupełnienie pyta, czy instancja jest instancją nie , co oznacza, że dopełnienie jest współinstancją. Każda instancja tak dla pierwotnego problemu NP staje się instancją nie dla jego uzupełnienia i na odwrót.
Niezadowolenie
Przykładem problemu NP-zupełnego jest problem spełnialności Boole'a : czy biorąc pod uwagę formułę Boole'a, jest on spełnialny (czy istnieje możliwe dane wejściowe, dla których formuła daje prawdę)? Problem komplementarny pyta: „Czy biorąc pod uwagę formułę Boole'a, jest ona niezadowalająca (czy wszystkie możliwe dane wejściowe do formuły wyprowadzają fałszywe)?”. Ponieważ jest to uzupełnienie problemu spełnialności, certyfikat dla instancji nie jest tym samym, co dla instancji tak z oryginalnego problemu NP: zbiór przypisań zmiennych logicznych, które sprawiają, że formuła jest prawdziwa. Z drugiej strony zaświadczenie o wystąpieniu tak dla problemu komplementarnego byłoby równie złożone, jak w przypadku wystąpienia nie oryginalnego problemu spełnialności NP.
Podwójne problemy
współ-NP-zupełność
Problem L jest ko-NP-zupełny , wtedy i tylko wtedy, gdy L jest współ-NP i problemu w porozumieniu NP, istnieje ograniczenie czasu wielomianowego od tego problemu do L .
Redukcja tautologii
Ustalenie, czy formuła w logice zdań jest tautologią, jest współ-NP-zupełne: to znaczy, czy formuła jest prawdziwa przy każdym możliwym przypisaniu jej zmiennym.
Stosunek do innych klas
P , klasa wielomianowych problemów rozwiązywalnych w czasie, jest podzbiorem zarówno NP, jak i współ-NP. Uważa się, że P jest podzbiorem ścisłym w obu przypadkach (i wyraźnie nie może być ścisłe w jednym przypadku, a nie ścisłe w drugim).
Uważa się również, że NP i co-NP są nierówne. Jeśli tak, to żaden problem NP-zupełny nie może być współ-NP i żaden problem współ-NP-zupełny nie może znajdować się w NP. Można to przedstawić w następujący sposób. Załóżmy, ze względu na sprzeczność, istnieje problem NP-zupełny X, który jest współ-NP. Ponieważ wszystkie problemy w NP można sprowadzić do X , wynika z tego, że dla każdego problemu w NP możemy skonstruować niedeterministyczną maszynę Turinga, która decyduje o swoim dopełnieniu w czasie wielomianowym; tj. NP ⊆ współ-NP. Z tego wynika, że zbiór dopełnień problemów w NP jest podzbiorem zbioru dopełnień problemów w ko-NP; tj. co-NP ⊆ NP. Zatem współ-NP = NP. Dowód, że żaden problem współ-NP-zupełny nie może być w NP, jeśli NP ≠ współ-NP jest symetryczny.
Faktoryzacja liczb całkowitych
Przykładem problemu, o którym wiadomo, że należy zarówno do NP, jak i do ko-NP (ale nie wiadomo, że należy do P) jest faktoryzacja liczb całkowitych : biorąc pod uwagę dodatnie liczby całkowite m i n , określ, czy m ma współczynnik mniejszy niż n i większy niż jeden . Członkostwo w NP jest jasne; jeśli m ma taki faktor, to sam faktor jest certyfikatem. Członkostwo w co-NP jest również proste: można po prostu wymienić czynniki pierwsze m , wszystkie większe lub równe n , które weryfikator może potwierdzić przez mnożenie i test pierwszości AKS . Obecnie nie wiadomo, czy istnieje algorytm wielomianowy do faktoryzacji, równoważny faktoryzacji liczb całkowitych w P, a zatem ten przykład jest interesujący jako jeden z najbardziej naturalnych problemów, o których wiadomo, że występują w NP i współ-NP, ale nie wiadomo, czy być w P.