Test Arka

Przedmiot & Z³o¿ono¶æ obliczeniowa

Modu³ & 13

Tytu³ & Pamiêæ logarytmiczna i hierarchia wielomianowa

Opracowanie & Przemys³aw Broniek

{ Syllabus}

Pamiêæ logarytmiczna i hierarchia wielomianowa

• klasy L, NL i coNL,

• Twierdzenie Immermana-Szelepcsényi'ego,

• klasy coNP i DP,

• maszyny alternuj±ce,

• hierarchia wielomianowa.

Klasy L, NL i coNL

W tym rozdziale zajmiemy siê klasami z³o¿ono¶ci, w których dajemy bardzo restrykcyjne wymagania odno¶nie zu¿ywanej pamiêci, a mianowicie ograniczamy jej ilo¶æ przez funkcjê logarytmiczn±. Przypomnijmy:

• Klasa L = SPACE(log$n$), to klasa tych jêzyków, które mog± byæ akceptowane w deterministycznej pamiêci logarytmicznej,

• Klasa NL = NSPACE(log$n$), to klasa tych jêzyków, które mog± byæ akceptowane w niedeterministycznej pamiêci logarytmicznej,

• Klasa coNL = coNSPACE(log$n$), to dope³nienie klasy tych jêzyków, które mog± byæ akceptowane w niedeterministycznej pamiêci logarytmicznej,

Na podstawie nastêpnego rozdzia³u i twierdzenia Immermana-Szelepcsényi'ego dowiemy siê, ¿e NL=coNL . Natomiast pytanie czy L=NL pozostaje wci±¿ problemem otwartym.

Przyjrzymy siê teraz problemom zupe³nym w klasie NL. Zupe³no¶æ definiujemy przy pomocy redukcji w pamiêci logarytmicznej, gdy¿ jak wiemy, wszystkie z powy¿szych klas s± zawarte w klasie P (chocia¿ nie wiemy, czy ¶ci¶le). Dopuszczenie redukcji wielomianowej zniwelowa³oby jakiekolwiek ró¿nice pomiêdzy jêzykami, gdy¿ sama redukcja mia³aby moc obliczeniow± pozwalaj±c± rozwi±zaæ wszystkie problemy z tych klas. Poni¿szy problem okazuje siê byæ NL-zupe³ny:

Definicja [Uzupelnij]

Problem REACHABILITY:
Wej¶cie: Graf skierowany $G$ oraz wierzcho³ki $x$ i $y$.
Wyj¶cie: Czy istnieje ¶cie¿ka od $x$ do $y$ w $G$?

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Bardzo ciekawy rezultat, który zbli¿y³ nas do odpowiedzi na pytanie czy L=NL, uzyska³ w 2004 Reingold. Pokaza³ on, ¿e problem UNDIRECTED REACHABILITY, czyli osi±galno¶æ w grafie nieskierowanym nale¿y do klasy L.

Twierdzenie Immermana-Szelepcsényi'ego

Ten rozdzia³ po¶wiêcony jest bardzo ciekawemu i ca³kiem m³odemu wynikowi udowodnionemu niezale¿nie przez Neila Immermana i Róberta Szelepcsényi'ego w roku 1987, za który otrzymali w 1995 nagrodê Gödel'a.

Twierdzenie mówi o tym, ¿e klasy niedeterministyczne z³o¿ono¶ci pamiêciowej s± zamkniête na dope³nienie:

Twierdzenie [Uzupelnij]

{{{3}}}

Dowód [Uzupelnij]

{{{3}}}

Klasy coNP i DP

Wprowadzili¶my ju¿ zarówno klasê NP jak i pojêcie dope³nieñ klas. Przyjrzyjmy siê bli¿ej klasie coNP. Klasa NP, jest to zbiór tych jêzyków, dla których mo¿emy ³atwo weryfikowaæ przynale¿no¶æ s³ów. Klasa coNP natomiast, to zbiór tych jêzyków, dla których mo¿emy ³atwo weryfikowaæ, ¿e s³owo nie nale¿y do jêzyka.

Podobnie jak dla NP i twierdzenia Fagina, mo¿na scharakteryzowaæ coNP jako zbiór w³asno¶ci teoriografowych wyra¿alnych w uniwersalnej logice drugiego rzêdu.

Oto przyk³ady problemów z klasy coNP:

Definicja [Uzupelnij]

Problem TAUTOLOGY:
Wej¶cie: formu³a logiczna $\varphi$ jak dla problemu SAT.
Wyj¶cie: czy ka¿de warto¶ciowanie spe³nia $\varphi$?

Definicja [Uzupelnij]

Problem HAMILTON PATH COMPLEMENT:
Wej¶cie: graf nieskierowany $G$.
Wyj¶cie: czy $G$ nie zawiera ¶cie¿ki Hamiltona?

W powy¿szych problemach weryfikacja negatywna s³owa wej¶ciowego jest ³atwa, bo opiera siê na zgadniêciu warto¶ciowania niespe³niaj±cego lub ¶cie¿ki Hamiltona.

Nietrudno udowodniæ (patrz æwiczenie koñcowe), ¿e s± to problemy zupe³ne dla klasy coNP. Nie jest to nic zaskakuj±cego, bowiem równie prosto mo¿na udowodniæ, ¿e je¿eli $L$ jest NP-zupe³ny, to jego dope³nienie $\bar{L}$ jest coNP-zupe³ne.

Jak wiele pytañ w teorii z³o¿ono¶ci obliczeniowej równie¿ i to, czy NP=coNP pozostaje otwarte. Mo¿emy jedynie stwierdziæ, ¿e je¿eli P=NP, to NP=coNP, gdy¿ P jest zamkniêta na dope³nienie. Jednak ju¿ implikacja w drug± stronê nie jest znana. Inna podobna implikacja to:

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Poni¿szy rysunek przedstawia relacje pomiêdzy poznanymi klasami i omawian± za chwilê klas± DP:

{1cm}

[width=10cm]{ZO-13-1-rys.jpg}
Relacje pomiêdzy klasami NP, coNP i DP

{1cm}

Oczywi¶cie przygl±daj±c siê wszystkim takim rysunkom nale¿y pamiêtaæ, ¿e mog± one w wielu miejscach kolapsowaæ.

Klasa DP

Zastanówmy siê nad nastêpuj±cym problemem:

Przykład [Uzupelnij]

Problem EXACT TSP:
Wej¶cie: graf nieskierowany wa¿ony $G$ i liczba $K$
Wyj¶cie: czy optymalna trasa komiwoja¿era dla $G$ ma warto¶æ dok³adnie $K$?

Jest to wersja dok³adna znanego problemu optymalizacyjnego -- problemu komiwoja¿era. Wiemy ¿e wersja decyzyjna TSP(D) jest NP-zupe³na. Nietrudno pokazaæ równie¿, ¿e EXACT TSP i TSP(D) s± wielomianowo równowa¿ne (æwiczenie koñcowe), tzn., ¿e je¶li jeden z nich ma rozwi±zanie w czasie wielomianowym to drugi te¿. W tym rozdziale sklasyfikujemy z³o¿ono¶æ EXACT TSP dok³adniej przy pomocy klasy DP. Nie umiemy bowiem pokazaæ, ¿e EXACT TSP nale¿y do NP, wszak jak po¶wiadczyæ i szybko zweryfikowaæ, ¿e d³ugo¶æ optymalnej trasy wynosi dok³adnie $K$? Widzimy, ¿e odpowied¼ na to pytanie wymaga stwierdzenia, ¿e trasa ma d³ugo¶æ co najmniej $K$ i co najwy¿ej $K$, co sugeruje pewne specyficzne po³±czenie problemu TSP(D) i jego dope³nienia.

Definicja [Uzupelnij]

Klasa DP to zbiór jêzyków $L$ takich, ¿e $L=L_1\cap L_2$, gdzie $L_1\in NP$ natomiast $L_2\in coNP$.

Przy tak postawionej definicji EXACT TSP nale¿y do DP. Jest on bowiem przeciêciem jêzyka TSP(D) i TSP(D) COMPLEMENT, tzn. koszt trasy wynosi dok³adnie $K$, gdy jest równy co najwy¿ej $K$ (to przynale¿no¶æ do TSP(D)) oraz co najmniej $K$ (to przynale¿no¶æ s³owa do TSP(D) COMPLEMENT).

Klasa DP posiada problemy zupe³ne. Rozwa¿my problem nastêpuj±cy:

Przykład [Uzupelnij]

Problem SAT-UNSAT:
Wej¶cie: formu³y logiczne $\varphi$ i $\psi$ jak dla SAT.
Wyj¶cie: czy formu³a $\varphi$ jest spe³nialna, natomiast $\psi$ niespe³nialna?

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Równie¿ wspomniany na pocz±tku problem EXACT TSP jest DP-zupe³ny. Mo¿na rozwa¿aæ tak¿e wiele innych wersji EXACT znanych problemów NP-zupe³nych, które okazuj± siê DP-zupe³ne.

Klasa DP zawiera tak¿e problemy DP-zupe³ne innego rodzaju:

Przykład [Uzupelnij]

Problem CRITICAL SAT:
Wej¶cie: formu³a logiczna $\varphi$ jak dla SAT.
Wyj¶cie: czy formu³a $\varphi$ jest nie spe³nialna, natomiast usuniêcie dowolnej klauzuli sprawia, ¿e jest spe³nialna?

Przykład [Uzupelnij]

Problem CRITICAL HAMILTON PATH:
Wej¶cie: graf nieskierowany $G$
Wyj¶cie: czy $G$ nie ma ¶cie¿ki Hamiltona, natomiast dodanie dowolnej krawêdzi do $G$ powoduje, ¿e ju¿ j± posiada?

Maszyny alternuj±ce

W tym rozdziale przedstawimy ciekawe uogólnienie niedeterminizmu, zwane alternacj±. Przypomnijmy, ¿e maszyna niedeterministyczna akceptuje s³owo, gdy na którejkolwiek ze ¶cie¿ek obliczeñ trafi do stanu akceptuj±cego.

Maszyna alternuj±ca ma wiêcej mo¿liwo¶ci. Ka¿dy z jej stanów jest oznaczony poprzez "AND" lub "OR", które nazywamy odpowiednio stanami uniwersalnymi i egzystencjalnymi.

Gdy maszyna jest w stanie typu "OR", to dokonuje akceptacji gdy dowolna ze ¶cie¿ek obliczeñ wychodz±cych z niego akceptuje s³owo. Tak w³a¶nie dzia³aj± zawsze zwyk³e maszyny niedeterministyczne.

Stany typu "AND" s± rozszerzaj± t± funkcjonalno¶æ. Maszyna dokonuje akceptacji bêd±c w takim stanie, gdy ka¿da ze ¶cie¿ek obliczeñ wychodz±cych z tego stanu jest akceptuj±ca.

Miarê z³o¿ono¶ci czasowej i pamiêciowej maszyn alternuj±cych definiujemy zupe³nie tak jak dla maszyn niedeterministycznych, tzn. funkcja $f(n)$ jest miar± z³o¿ono¶ci czasowej, gdy ka¿da ze ¶cie¿ek obliczeñ ma d³ugo¶æ ograniczon± przez $f(n)$ oraz z³o¿ono¶æ pamiêciow± $f(n)$ gdy na ka¿dej ze ¶cie¿ek obliczeñ maszyna zu¿ywa co najwy¿ej $f(n)$ pamiêci.

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{ATIME}(f(n))} oznaczamy zbiór jêzyków $L$ takich, ¿e s± akceptowane przez alternuj±c± maszynê Turinga $M$ o z³o¿ono¶ci czasowej $f(n)$.

Definicja [Uzupelnij]

Poprzez Parser nie mógł rozpoznać (nieznana funkcja „\textsc”): {\displaystyle \textsc{ASPACE}(f(n))} oznaczamy zbiór jêzyków $L$ takich, ¿e s± akceptowane przez alternuj±c± maszynê Turinga $M$ o z³o¿ono¶ci pamiêciowej $f(n)$.

Wprowadzamy te¿ skróty dla najpopularniejszych klas:

• Klasa AP = ATIME $(n^k)=\bigcup _{j>0}$ ATIME $(n^j)$, to klasa tych jêzyków, które mog± byæ akceptowane w alternuj±cym czasie wielomianowym,

• Klasa AL = ASPACE(log$n$), to klasa tych jêzyków, które mog± byæ akceptowane w alternuj±cej pamiêci logarytmicznej,

Nietrudno siê domy¶liæ, ¿e alternacja jest silniejsza ni¿ niedeterminizm z definicji dzia³ania maszyn. Wiemy zatem, w szczególno¶ci, ¿e $AP$ zawiera w sobie $NP$. Poni¿sze æwiczenie pokazuje, ¿e o AP mo¿na powiedzieæ wiêcej:

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

To jednak nie wszystko co potrafi klasa AP. Znajduj± siê w niej jêzyki, o których nie wiemy czy nale¿± do NP lub coNP.

Definicja [Uzupelnij]

Problem MIN-FORMULA:
Wej¶cie: formu³a logiczna $\varphi$ jak dla problemu SAT.
Wyj¶cie: czy $\varphi$ jest minimalna, tzn. czy ¿adna krótsza formu³a nie jest jej równowa¿na?

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Teraz przedstawimy kilka relacji pomiêdzy klasami obliczeñ alternuj±cych:

Twierdzenie [Uzupelnij]

Nastêpuj±ce relacje s± prawdziwe:

1. Je¶li $f(n)⩾n$ to ATIME $(f(n))\subseteq$ SPACE $(f(n))$,

1. Je¶li $f(n)⩾n$ to SPACE $(f(n))\subseteq$ ATIME $(f^2(n))$,

1. Je¶li $f(n)⩾$ log $n$ to ASPACE $(f(n))\subseteq$ TIME $(c^{f(n)})$.

1. Je¶li $f(n)⩾$ log $n$ to ASPACE $(f(n))\supseteq$ TIME $(c^{f(n)})$.

Dowód [Uzupelnij]

{{{3}}}

Dziêki wymienionym relacjom pomiêdzy klasami alternuj±cymi mo¿emy udowodniæ kilka dok³adnych równo¶ci pomiêdzy klasami, a to rzadka rzecz w teorii z³o¿ono¶ci. Wiemy zatem, ¿e:

• AL=P,

• APSPACE = EXP,

• AP=PSPACE.

Hierarchia wielomianowa

W tej czê¶ci zdefiniujemy ca³± hierarchiê klas ponad znanymi nam ju¿ P i NP, która stanowi pewne uogólnienie problematyki spotkanej w klasie DP.

W poprzednich rozdzia³ach zdefiniowali¶my pojêcie maszyny z wyroczni± na jêzyk $L$ oznaczanej przez $M^L$. Przypomnijmy, ¿e jest to zwyk³a maszyna $M$ z dodatkow± mo¿liwo¶ci± zadania pytania postaci "czy $x\in L$?" które kosztuje jedn± jednostkê czasu. Rozszerzenie tego pojêcia na klasy jest naturalne. Poprzez $P^{NP}$ oznaczamy zbiór tych jêzyków, które mog± byæ rozstrzygane przez maszyny z klasy $P$ z wyroczni± na dowolny jêzyk z klasy $NP$.

Ta klasa okazuje siê byæ mocniejsza od DP, bowiem w DP mogli¶my zadañ pytanie tylko raz (dotycz±ce coNP, ale w sensie wyroczni dzia³a to jak pytanie do NP), a tutaj dowoln± liczbê razy i to na dodatek pytañ adaptywnych, tzn. takich, które mog± zale¿eæ od wyników odpowiedzi na poprzednie z nich. Kolejn± interesuj±c± klas± jest $N{P}^{NP}$. Wszystkie te klasy daj± nam coraz wiêksze mo¿liwo¶ci, lecz oczywi¶cie nie wiadomo, czy s± to ¶ci¶le wiêksze klasy, choæ panuje takie przekonanie:

{1cm}

[width=10cm]{ZO-13-3-rys.jpg}
Klasy relatywne

{1cm}

Postêpuj±c w ten sposób Meyer i Stockmeyer w latach 70 zdefiniowali ca³± hierarchiê klas:

Definicja [Uzupelnij]

Hierarchia wielomianowa, to ci±g klas indeksowany poprzez $i$:

• $\sum _{0}P=\prod _{0}P={\mathrm{\Delta }}_{0}P=P$

• ${\mathrm{\Delta }}_{i+1}P=P^{\sum _{i}P},$ dla $i>0$,

• $\sum _{i+1}P=N{P}^{\sum _{i}P},$ dla $i>0$,

• $\prod _{i+1}P=coN{P}^{\sum _{i}P},$ dla $i>0$.

Dodatkowo poprzez $PH$ oznaczamy sumê wszystkich tych klas, czyli:
$PH=\bigcup _{i⩾0}\sum _{i}P$.

Poniewa¿ na poziomie zerowym wszystkie elementy hierarchii to P, wiêc na poziomie pierwszym, poniewa¿ taka wyrocznia nic nie daje, otrzymujemy ${\mathrm{\Delta }}_{1}P=P,\sum _{1}P=NP,\prod _{1}P=coNP$. Drugi poziom, to klasy${\mathrm{\Delta }}_{2}P=P^{NP},\sum _{2}P=N{P}^{NP},\prod _{2}P=coN{P}^{NP}$. Warto zwróciæ uwagê, ¿e $\prod _{i}P$ jest dope³nieniem $\sum _{i}P$ na ka¿dym poziomie wprost z definicji. Zawieranie siê poszczególnych elementów na jednym poziomie obrazuje poni¿szy rysunek:

{1cm}

[width=10cm]{ZO-13-4-rys.jpg}
Hierarchia wielomianowa

{1cm}

Do tej pory czêsto odwo³ywali¶my siê do odpowiednio¶ci pomiêdzy klas± NP a szczególnymi relacjami wielomianowo zrównowa¿onymi i rozstrzygalnymi. Przedstawimy teraz zgrabn± charakteryzacjê klas z hierarchii wielomianowej przy pomocy podobnego kryterium:

Twierdzenie [Uzupelnij]

Niech $L$ bêdzie jêzykiem, $i>0$. Jêzyk $L$ nale¿y do $\sum _{i}P$ wtedy i tylko wtedy, gdy istnieje wielomianowo zrównowa¿ona i rozstrzygalna relacja $R$ ($i+1$-argumentowa), taka, ¿e $x\in L$ dok³adnie wtedy, gdy $\mathrm{\exists }{y}_1\mathrm{\forall }{y}_2\mathrm{\exists }{y}_3\dots Q{y}_i$ takie, ¿e $R(x,y_1,\dots ,y_i)$ jest spe³nione ($i$-ty kwantyfikator jest uniwersalny, gdy $i$ jest parzyste, natomiast egzystencjalny, gdy $i$ jest nieparzyste).

Hierarchia wielomianowa jest struktur± dosyæ wra¿liw± na kolapsy, tzn. równo¶ci klas na pewnym poziomie. Okazuje siê, ¿e wtedy przenosz± siê one automatycznie w górê:

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Zachodzi równie¿ podobny fakt. Otó¿, je¶li P=NP (albo tylko NP=coNP), to hierarchia kolapsuje ju¿ na pierwszym poziomie.

Mo¿na by siê zastanowiæ, czy kolejne poziomy hierarchii wielomianowej s± interesuj±ce z punku widzenia problemów, które pozwalaj± one rozwi±zaæ. Okazuje siê, ¿e na ka¿dym poziomie hierarchii posiada ona problemy zupe³ne:

Definicja [Uzupelnij]

Problem QSAT ${}_i$:
Wej¶cie: formu³a logiczna $\varphi$ jak dla problemu SAT poprzedzona $i$ naprzemiennymi grupami kwantyfikatorów egzystencjalnych i uniwersalnych: $\mathrm{\Phi }=\mathrm{\exists }{x}_1\mathrm{\forall }{x}_2\mathrm{\exists }{x}_3\dots Q{x}_i\varphi$.
Wyj¶cie: czy $\mathrm{\Phi }$ jest prawdziwa?

Twierdzenie [Uzupelnij]

Problem $QSA{T}_i$ jest $\sum _{i}P$-zupe³ny dla $i>0$.

Jednak pytanie czy istnieje problem PH-zupe³ny (czyli zupe³ny dla ca³ej hierarchii) jest otwarte i panuje przekonanie, ¿e tak nie jest, gdy¿:

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Jak silna jest ca³a hierarchia? Mo¿na ³atwo zauwa¿yæ, ¿e zawiera siê ona w znanej ju¿ nam klasie PSPACE, ze wzglêdu na fakt, ¿e mo¿na ³atwo rozstrzygaæ w wielomianowej pamiêci relacje, charakteryzuj±ce problemy z PH, które opisywali¶my wcze¶niej.

Jak nietrudno siê domy¶liæ pytanie, czy PH=PSPACE jest otwarte. Bardzo interesuj±ce jest jednak, ¿e gdyby równo¶æ zachodzi³a, to poniewa¿ PSPACE zawiera problemy zupe³ne, to PH równie¿ by je zawiera³a, st±d zapad³a by siê na pewnym skoñczonym poziomie. St±d przekonanie, ¿e PH zawiera siê silnie w PSPACE.

Na koniec ciekawy rezultat autorstwa Seinosuke Tody (laureata nagrody Gödel'a z roku 1998) zwi±zany z klas± PH. Pokaza³ on, ¿e $PH\subseteq P^{PP}$, czyli wyrocznia na klasê $PP$ jest niesamowicie silna i pozwala poch³on±æ tak misternie zbudowan± piramidê coraz silniejszych klas.

Æwiczenia dodatkowe

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}

Ćwiczenie

{{{3}}}

Wskazówka

{{{3}}}

Rozwiązanie

{{{3}}}