Dopełnienie argumentu

W teorii złożoności obliczeniowej argument dopełnienia jest narzędziem do warunkowego udowodnienia, że ​​jeśli niektóre klasy złożoności są równe, to niektóre inne większe klasy również są równe.

Przykład

Dowód, że P = NP implikuje EXP = NEXP, wykorzystuje „dopełnienie”.

${\ Displaystyle \ operatorname {EXP} \ subseteq \ operatorname {NEXP}}$ z definicji, więc wystarczy pokazać ${\ displaystyle \ operatorname {NEXP} \ subseteq \mathrm {EXP} }$ .

Niech L będzie językiem w NEXP. Ponieważ L $jest$ w NEXP, istnieje niedeterministyczna maszyna Turinga , która decyduje o L w czasie pewnej stałej . Pozwalać

${\ Displaystyle L '= \ {x1 ^ {2 ^ {| x | ^ {c}}} \ środkowy x \ w L \},}$

gdzie „1” jest symbolem nie występującym w L . Najpierw pokażemy, że ${\ displaystyle L'}$ jest w NP, a następnie użyjemy deterministycznej wielomianowej maszyny czasu określonej przez P = NP, aby pokazać, że L jest w EXP.

${\ displaystyle L '}$ można rozstrzygnąć w niedeterministycznym czasie wielomianowym w następujący sposób. Biorąc pod uwagę dane wejściowe $,$ on postać ${\ Displaystyle x'=x1 ^ {2 ^ {| x | ^ {c}}}}$ i odrzuć, jeśli tak nie jest. Jeśli ma poprawną postać, zasymuluj M ( x ). Symulacja przyjmuje niedeterministyczne ${\ Displaystyle 2 ^ {| x | ^ {c}}}$ czas, który jest wielomianem wielkości danych wejściowych, ${\ Displaystyle x'}$ . Więc ${\ displaystyle L'}$ jest w NP. $DM$ = NP istnieje również deterministyczna maszyna , która decyduje w czasie wielomianowym. Możemy wtedy zdecydować o L w deterministycznym czasie wykładniczym w następujący sposób. Biorąc pod uwagę dane $,$ symuluj ${\ Displaystyle DM (x1 ^ {2 ^ {| x | ^ {c}}})}$ . Zajmuje to tylko wykładniczy czas w rozmiarze danych wejściowych, ${\ displaystyle x}$ .

$.$ to „ wypełnieniem” języka L Ten typ argumentu jest również czasami używany w przypadku klas złożoności przestrzeni , klas naprzemiennych i ograniczonych klas naprzemiennych.

•   Arora, Sanjeev ; Barak, Boaz (2009), Złożoność obliczeniowa: nowoczesne podejście , Cambridge , s. 57, ISBN 978-0-521-42426-4