Dopełnienie (teoria złożoności)

Z Wikipedii

W teorii złożoności obliczeniowej, dopełnienie problemu decyzyjnego to problem decyzyjny powstający po zamianie miejscami odpowiedzi tak i nie. Równoważnie, jeśli zdefiniujemy proces decyzyjny jako zbiór skończonych napisów, dopełnienie zbioru tych napisów nad ich alfabetem jest dopełnieniem problemu.

Przykładowo, jeśli rozważymy problem decyzyjny określania czy dana liczba jest liczbą pierwszą, to dopełnieniem tego problemu będzie określanie czy dana liczba jest liczbą złożoną.

Uogólniając tę operację na klasy złożoności obliczeniowej, możemy wprowadzić klasy będące dopełnieniem problemów w danej klasie. Jeśli pierwotna klasa nazywa się C, jej klasa dopełniająca nazywa się Co-C. Należy pamiętać że nie jest ona dopełnieniem tej klasy jako zbioru problemów – dopełnienie takie zawiera zwykle znacznie więcej problemów.

Klasa złożoności może być zamknięta na dopełnienie jeśli dopełnienie każdego problemu w tej klasie należy do tej klasy. Ponieważ istnienie redukcja Turinga z każdego problemu do jego dopełnienia, każda klasa zamknięta na redukcje Turinga jest zamknięta na dopełnienie. Każda klasa zamknięta na dopełnienie jest równa swojej klasie dopełniającej. W szczególności wszystkie klasy deterministyczne DSPACE(f(n)), DTIME(f(n)) dla wszystkich f(n)) są zamknięte na dopełnienie, ponieważ można zawsze dodać ostatni krok do maszyny Turinga, który odwraca odpowiedź. Ta metoda nie działa dla niedeterministycznych klas, ponieważ jeśli istnieją ścieżki obliczeń zarówno akceptujące jak i nieakceptujące, odwrócenie odpowiedzi na końcu każdego obliczenia nic nie zmienia – w obu przypadkach maszyna odpowiada akceptująco.

Wiele istotnych klas jest uważana za różne od swoich dopełnień. W szczególności NP uważa się za różne od Co-NP, choć nie jest to udowodnione.

Jednym z najbardziej zaskakujących rezultatów w teorii złożoności jest Twierdzenie Immerman-Szelepcsényi, pokazujące że wszystkie niedeterministyczne klasy pamięciowe (NSPACE) są zamknięte na dopełnienie.