dopełnienie

Dopełnienie – 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 nazywana jest C, jej klasa dopełniająca jest nazywana 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)) i 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żanych za różne od swoich dopełnień. W szczególności NP uważa się za różne od Co-NP, choć nie zostało to udowodnione. Jednym z najbardziej zaskakujących rezultatów w teorii złożoności jest pokazujące, że wszystkie niedeterministyczne klasy pamięciowe NSPACE są zamknięte na dopełnienie.