Złożoność obliczeniowa/Wykład 15: Kryptografia a złożoność

From Studia Informatyczne

Funkcje jednokierunkowe

W dotychczasowych rozważaniach naszym celem było znalezienie możliwie efektywnego rozwiązania dla zadanych problemów; nadmierna złożoność problemu była przez nas traktowana jako cecha niepożądana, utrudniająca nam zadanie. W tym rozdziale nasze podejście będzie odmienne; duża złożoność będzie dla nas cechą bardzo cenną. Będzie nas przy tym, w mniejszym niż dotychczas stopniu, interesować złożoność pesymistyczna -- w końcu nie satysfakcjonuje nas "gwarancja" mówiąca, że "jeżeli osoba podsłuchująca będzie miała pecha, to odszyfrowanie wiadomości będzie dla niej zadaniem czasochłonnym". Wolelibyśmy, żeby odszyfrowywanie wiadomości przez osoby nieuprawnione było czasochłonne, praktycznie zawsze -- tak, by próba podsłuchiwania dawała szansę sukcesu bardzo bliską zeru. Duża pesymistyczna złożoność nie będzie zatem warunkiem wystarczającym bycia dobrym kryptosystemem; przyda nam się jednak w charakterze warunku koniecznego.

Definicja 1.1

Niech \displaystyle f: \{ 0, 1 \} ^\star \rightarrow \{ 0, 1 \} ^\star. Mówimy, że \displaystyle f jest funkcją jednokierunkową wtedy i tylko wtedy, gdy:

  • \displaystyle f jest różnowartościowa,
  • istnieje pewna stała \displaystyle k > 1 taka, że \displaystyle \forall_{x \in \{0, 1\}^\star} |x|^{1/k} \leq f(x) \leq |x|^k,
  • \displaystyle f jest obliczalna w czasie wielomianowym (czyli należy do klasy \displaystyle FP),
  • nie istnieje wielomianowy algorytm obliczający odwrotność funkcji \displaystyle f -- czyli znajdujący dla słowa \displaystyle y słowo \displaystyle x, takie że \displaystyle f(x) = y lub stwierdzający, że takie słowo nie istnieje.

Warto zauważyć, że powyższa definicja niejawnie zakłada prawdziwość zdania \displaystyle P \neq NP.

Ćwiczenie 1.2

Niech \displaystyle f spełnia pierwsze trzy warunki podane w definicji funkcji jednokierunkowej. Pokaż, że obliczanie odwrotności funkcji \displaystyle f jest problemem z klasy \displaystyle FNP.

Rozwiązanie

Z drugiego warunku wiemy, że \displaystyle f^{-1}(y) ma długość co najwyżej \displaystyle |y|^k. Możemy zatem jako kandydatów na świadków rozpatrywać wszystkie słowa o długości nie większej niż \displaystyle |y|^k. Takie słowa możemy następnie deterministycznie przekształcić za pomocą funkcji \displaystyle f i sprawdzić, czy otrzymane słowo jest równe \displaystyle y.

Z drugiej strony nierówność \displaystyle P \neq NP wcale nie gwaratuje istnienia funkcji jednokierunkowych; jak się okazuje istnienie tego typu funkcji jest ściśle powiązane z pewną klasą złożoności, którą przedstawiamy poniżej.

Definicja 1.3

Jednoznaczną maszyną Turinga nazywamy niedeterministyczną maszynę Turinga taką, że dla każdego słowa wejściowego \displaystyle x istnieje co najwyżej jedna akceptująca ścieżka obliczeń.

Definicja 1.4

Klasa \displaystyle UP to klasa problemów rozstrzygalnych za pomocą jednoznacznych maszyn Turinga w czasie wielomianowym.

Uwaga 1.5

Klasę \displaystyle UP, podobnie jak klasę \displaystyle NP, można zdefiniować z użyciem pojęcia świadka:

\displaystyle L \in UP \iff \exists_{p(x) - wielomian} \exists_{L' \in P} \forall_{n \in {\mathbb N}} \forall_{w \in \{ 0, 1 \} ^n} [w \in L \Rightarrow ({\exists !}_{v \in \{ 0, 1 \}^{p(n)}} \langle w, v \rangle \in L')] \wedge [w \notin L \Rightarrow (\neg \exists_{v \in \{ 0, 1 \}^{p(n)}} \langle w, v \rangle \in L')].

W językach z klasy \displaystyle UL każde słowo ma dokładnie jednego świadka. Dowód równoważności powyższych definicji jest analogiczny jak w przypadku klasy \displaystyle NP.

Jest jasne, że \displaystyle P \subseteq UP \subseteq NP -- maszyny deterministyczne są specjalnymi przypadkami maszyn jednoznacznych. Dość powszechny jest pogląd, że obie powyższe relacje zawierania są właściwe (to znaczy nie zachodzi równość).

Pokażemy teraz bardzo ciekawy związek pomiędzy klasą \displaystyle UP a funkcjami jednokierunkowymi.

Twierdzenie 1.6

Funkcje jednokierunkowe istnieją wtedy i tylko wtedy, gdy \displaystyle UP \neq P.

Dowód

Zaczniemy od dowodu w kierunku \displaystyle \Rightarrow. Załóżmy, że istnieje pewna funkcja jednokierunkowa \displaystyle f. Możemy wtedy zdefiniować następujący język:

\displaystyle L_f = \{ (x, y): \exists_z f(z) = y \wedge z \leq x\},

przy czym mówimy, że \displaystyle z \leq x wtedy i tylko wtedy, gdy

  • \displaystyle |z| \leq |y| lub
  • \displaystyle |z| = |y| i w porządku leksykograficznym \displaystyle z występuje nie później niż \displaystyle x.

Łatwo można zauważyć, że \displaystyle L_f \in UP - maszyna rozwiązująca ten problem najpierw "zgaduje" słowo \displaystyle z o wielkości nie większej niż \displaystyle |y|^k, po czym sprawdza, czy w ustalonym porządku występuje ono nie później niż \displaystyle x i czy zachodzi \displaystyle f(z) = y. Z własności funkcji jednokierunkowych -- konkretnie z różnowartościowości -- wynika, że maszyna ta ma co najwyżej jedną akceptującą ścieżkę postępowania.

Chcemy teraz pokazać, że \displaystyle L_f \notin P. Załóżmy zatem nie wprost, że istnieje jakiś wielomianowy algorytm rozwiązujący \displaystyle L_f. Wykorzystamy go teraz do obliczenia odwrotności funkcji \displaystyle f w czasie wielomianowym. W pierwszym kroku zapytamy algorytm, czy \displaystyle (1^{|y|^k}, y) \in L_f (przez \displaystyle 1^{|y|^k} oznaczamy tutaj ciąg \displaystyle |y|^k symboli \displaystyle 1) - jeżeli otrzymamy odpowiedź NIE, to korzystając z definicji funkcji jednokierunkowej, możemy od razu stwierdzić, że nie istnieje słowo \displaystyle x takie, że \displaystyle f(x) = y. Jeżeli otrzymamy odpowiedź TAK, to z użyciem co najwyżej \displaystyle |y|^k - 1 zapytań do naszego algorytmu jesteśmy w stanie ustalić długość szukanego słowa \displaystyle x (pytamy kolejno o \displaystyle (1^{|y|^k - 1}, y), \displaystyle (1^{|y|^k - 2}, y), itd., aż do momentu, gdy uzyskamy odpowiedź NIE). Gdy znamy już długość słowa \displaystyle x pozostaje nam tylko obliczyć kolejne jego bity. Pierwszy bit otrzymamy, pytając o parę \displaystyle (01^{|x| - 1}, y) -- odpowiedź "tak" oznacza, że pierwszym bitem jest 0. Aby uzyskać drugi bit zapytamy -- w zależności od pierwszej odpowiedzi -- o \displaystyle (001^{|x| - 2}, y) lub \displaystyle (101^{|x| - 2}, y). Kolejne bity odgadujemy w analogiczny sposób -- łącznie zatem wykonamy algorytm dla \displaystyle L_f\displaystyle O(|y|^k) razy. W ten sposób uzyskamy deterministycznty algorytm odwracający funkcję \displaystyle f w czasie wielomianowym.

Doszliśmy więc do sprzeczności z definicją funkcji jednokierunkowej, co oznacza, że istnienie funkcji jednokierunkowych implikuje nierówność \displaystyle P \neq UP.

Załóżmy teraz, że istnieje język \displaystyle L \in UP - P, rozpoznawany przez jednoznaczną maszynę \displaystyle U. Zdefiniujmy funkcję \displaystyle f_U(w) w następujący sposób:

  • jeżeli \displaystyle w jest zakodowaną parą słów \displaystyle \langle x, y \rangle oraz \displaystyle x jest (jedynym) świadkiem przynależności słowa \displaystyle y do \displaystyle L, to

\displaystyle f_U(w) = 1y,

  • w przeciwnym przypadku

\displaystyle f_U(w) = 0w.

Widzimy, że pierwszy symbol wartości funkcji gwarantuje nam jej różnowartościowość. Spełniony jest również drugi warunek z definicji funkcji jednokierunkowej -- świadek dla słowa \displaystyle y nie może być nadmiernie długi (bo jego długość jest wielomianowo zależna od długości \displaystyle y), a zatem \displaystyle f_U nie może nadmiernie "skracać" słów. Funkcja \displaystyle f_U jest też obliczalna w czasie wielomianowym -- wystarczy deterministycznie zweryfikować świadka, tak jak zrobiłaby to maszyna \displaystyle U. Pozostaje nam zatem tylko pokazanie, że funkcja odwrotna do \displaystyle d nie jest obliczalna w czasie wielomianowym. Gdyby tak jednak było, to moglibyśmy rozpoznawać język \displaystyle L w czasie wielomianowym: aby sprawdzić, czy \displaystyle y \in L wystarczy zastosować odwrotność funkcji \displaystyle f_U do słowa \displaystyle 1y; jeżeli \displaystyle y \notin L, to dostaniemy odpowiedź mówiącą, że \displaystyle 1y nie można odwrócić; w przeciwnym przypadku otrzymamy świadka przynależności \displaystyle y do języka \displaystyle L.

image:End_of_proof.gif

Na dzień dzisiejszy nie znamy oczywiście funkcji, o której wiedzielibyśmy, że jest jednokierunkowa; istnienie takiej funkcji natychmiastowo implikuje przecież nierówność \displaystyle P \neq NP. Jest jednak kilku "kandydatów" na funkcje jednokierunkowe, dla których nie znamy efektywnego algorytmu pozwalającego na ich odwrócenie. Jedną z takich funkcji jest \displaystyle f_{MUL}. Argumentami tej funkcji są dwie liczby pierwsze wraz ze swoimi certyfikatami pierwszości. Wartością funkcji jest iloczyn tych dwóch liczb. Bardziej formalnie:

  • jeżeli \displaystyle w = \langle p, C(p), q, C(q) \rangle, gdzie \displaystyle p < q a \displaystyle C(p) i \displaystyle C(q) są certyfikatami pierwszości odpowiednio dla \displaystyle p i \displaystyle q, to

\displaystyle f_{MUL}(w) = 1 p \cdot q,

  • w przeciwnym przypadku

\displaystyle f_{MUL}(w) = 0 w.

Korzystamy tutaj z faktu, że możemy wymusić jednoznaczną reprezentację certyfikatu pierwszości dla danej liczby oraz że certyfikaty mają rozmiar wielomianowo zależny od rozmiaru certyfikowanych liczb. \displaystyle f_{MUL} jest zatem różnowartościowa i nie "skraca" nadmiernie słowa wejściowego.

Łatwo zauważyć, gdzie tkwi trudność w odwracaniu tej funkcji -- nie znamy efektywnego algorytmu potrafiącego faktoryzować iloczyn dwóch liczb pierwszych; znane nam obecnie algorytmy stają się niepraktyczne już przy iloczynach liczb pierwszych o długości kilkuset bitów.

Drugi ze znanych nam "kandydatów na funkcję jednokierunkową" również oparty jest na zagadnieniu z dziedziny teorii liczb -- problemie logarytmu dyskretnego. Funkcję tą można zdefiniować w następujący sposób:

  • dla \displaystyle w postaci \displaystyle \langle p, C(p), r, x \rangle, gdzie \displaystyle p jest liczbą pierwszą, \displaystyle C(p) certyfikatem jej pierwszości, \displaystyle r jest najmniejszym generatorem grupy cyklicznej \displaystyle \mathbb{Z}_p^\star, a \displaystyle x jest liczbą naturalną z zakresu \displaystyle [1, p-1]

\displaystyle f_{EXP}(w) = 1 \langle p, r, r^x mod p)\rangle

  • dla pozostałych \displaystyle w

\displaystyle f_{EXP}(w) = 0 w.

W tym przypadku, aby odwrócić funkcję \displaystyle f_{EXP}, musielibyśmy na podstawie liczb \displaystyle p, \displaystyle r i \displaystyle r^x mod p umieć obliczyć wartość \displaystyle x. Również dla tego, znanego od wielu lat, problemu nie potrafimy przedstawić wydajnego rozwiązania.

Jak zauważyliśmy, we wprowadzeniu do tego rozdziału, w kryptografii duża złożoność pesymistyczna próby zdekodowania zaszyfrowanej wiadomości nie jest własnością wystarczającą. Z tego powodu przytoczymy alternatywną definicję funkcji jednokierunkowych, lepiej odwzorowującą nasze oczekiwania. Należy pamiętać, że definicja ta jest istotnie różna od definicji podanej wcześniej.

Definicja 1.7

Niech \displaystyle f: \{ 0, 1 \}^\star \rightarrow \{ 0, 1 \}^\star. Mówimy, że \displaystyle f jest funkcją jednokierunkową wtedy i tylko wtedy, gdy:

  • \displaystyle f jest obliczalna w czasie wielomianowym,
  • \displaystyle f nie jest stale równa \displaystyle \epsilon (słowu pustemu),
  • istnieje pewna stała \displaystyle k > 1 taka, że \displaystyle \forall_{x \in \{0, 1\}^\star} f(x) = \epsilon \vee |x|^{1/k} \leq f(x) \leq |x|^k,
  • jeżeli \displaystyle x i \displaystyle y są słowami nad alfabetem \displaystyle \{ 0, 1 \} i \displaystyle f(x) = f(y), to \displaystyle x = y lub \displaystyle f(x) = f(y) = \epsilon,
  • dla każdej losowej maszyny Turinga \displaystyle E działającej w czasie wielomianowym, każdej liczby \displaystyle l i dostatecznie dużej liczby \displaystyle n, jeżeli \displaystyle x jest losowym słowem ze zbioru \displaystyle \{ x': |x'| \leq n \wedge f(x') \neq \epsilon \}, to

\displaystyle Pr[E(f(x)) = x] \leq n^{-l}.

W tej definicji zrezygnowaliśmy z wymagania o różnowartościowości funkcji; zamiast tego dopuszczamy, aby różne słowa dawały jako wynik wartość \displaystyle \epsilon, którą możemy traktować jako odpowiedź mówiącą, że wejście jest nieprawidłowe; dla przykładu przy adaptowaniu funkcji \displaystyle f_{MUL} do powyższej definicji, w przypadku gdy \displaystyle p lub \displaystyle q nie będą liczbami pierwszymi lub gdy \displaystyle C(p), lub \displaystyle C(q) nie będą odpowiednimi certyfikatami, funkcja zwróci wartość \displaystyle \epsilon. Zauważmy, że w powyższej definicji interesuje nas tylko trudność odszyfrowania wartości funkcji dla poprawnych wejść -- to znaczy w przypadku \displaystyle f_{MUL} dla par liczb, które są pierwsze i których pierwszość jest potwierdzana przez \displaystyle C(p) i \displaystyle C(q). Funkcje \displaystyle f_{MUL} jak i \displaystyle f_{EXP} -- po odpowiednim ich zmodyfikowaniu w sposób przedstawiony powyżej -- są poważnymi "kandydatami" na funkcje jednokierunkowe również w sensie definicji opisanej w poprzednim paragrafie.

Warto się w tym momencie zastanowić, w jaki sposób funkcje jednokierunkowe mogą się przydać w kryptografii. Otóż widzimy, że jedna ze stron -- zwyczajowo zwana Alicją -- może wydajnie zaszyfrować swoją wiadomość, na przykład używając ją jako argument \displaystyle x do funkcji \displaystyle f_{EXP}. Niestety druga strona -- zazwyczaj o imieniu Bob -- może mieć duże trudności z odszyfrowaniem wiadomości. W tej sytuacji fakt, że osoba podsłuchująca -- Cecylia -- niczego ciekawego się nie dowie, stanowi słabe pocieszenie.

Widzimy zatem, że aby zapewnić poufność komunikacji pochodzącej od Alicji, ale również możliwość odebrania tej wiadomości, Bob musi posiadać pewną tajną wiedzę, pozwalającą na wydajne odwrócenie funkcji szyfrującej. Zdefiniujemy teraz pewną modyfikację pojęcia funkcji jednokierunkowej mającą szersze zastosowanie w kryptografii.

Definicja 1.8

Niech \displaystyle f: \{ 0,1 \}^\star \times \{ 0,1 \}^\star \rightarrow \{ 0,1 \}^\star. Mówimy, że \displaystyle f jest funkcją z wytrychem wtedy i tylko wtedy gdy istnieje losowa maszyna Turinga \displaystyle G oraz funkcja \displaystyle h:\{ 0,1 \}^\star \times \{ 0,1 \}^\star \rightarrow \{ 0,1 \}^\star taka, że:

  • funkcje \displaystyle f i \displaystyle h są obliczalne w czasie wielomianowym,
  • \displaystyle G oczekuje na wejściu słowa nad alfabetem \displaystyle \{ 0, 1\}, zwraca zakodowaną parę słów nad alfabetem \displaystyle \{0, 1\} i działa w czasie wielomianowym,
  • istnieje stała \displaystyle k > 1 taka, że jeżeli \displaystyle \langle i, t \rangle stanowi wynik działania maszyny \displaystyle M dla słowa \displaystyle 1^n, natomiast \displaystyle x jest słowem o długości nie większej niż \displaystyle n, to \displaystyle |\langle i, x \rangle |^{1/k} \leq |\langle t, f(i, x) \rangle | \leq |\langle i, x \rangle |^k,
  • jeżeli \displaystyle \langle i, t \rangle stanowi wynik działania maszyny \displaystyle M dla słowa \displaystyle 1^n, natomiast \displaystyle x i \displaystyle y są słowami o długości nie większej niż \displaystyle n, to

\displaystyle f(i,x) = f(i,y) \Rightarrow x=y,

  • dla każdej losowej maszyny Turinga \displaystyle E, każdej liczby \displaystyle l i dostatecznie dużej liczby \displaystyle n, jeżeli \displaystyle \langle i, t \rangle stanowi wynik działania maszyny \displaystyle M dla słowa \displaystyle 1^n, \displaystyle x jest losowym słowem nad alfabetem \displaystyle \{ 0, 1\} nie dłuższym niż \displaystyle n, to

\displaystyle Pr[E(i, f(i, x)) = x] \leq n^{-l},

  • dla każdego \displaystyle n, każdego słowa \displaystyle x nie dłuższego niż \displaystyle n i każdej pary \displaystyle \langle i, t \rangle mogącej być wynikiem działania maszyny \displaystyle G, dla słowa wejściowego \displaystyle 1^n\displaystyle h(t, f(i, x)) = x.

Funkcje z wytrychem mogą zostać wykorzystane w celu stworzenia systemów kryptograficznych z kluczem publicznym. Sposób postępowania jest w tym przypadku następujący:

  • Bob ustala długość przekazywanych wiadomości (\displaystyle n) oraz parametr wyznaczający prawdopodobieństwo odszyfrowania pojedynczej wiadomości (\displaystyle k),
  • Bob uruchamia maszynę \displaystyle G i otrzymuje parę słów \displaystyle \langle i, t\rangle. Słowo \displaystyle i staje się dostępnym dla wszystkich kluczem publicznym, natomiast \displaystyle t pozostaje tajemnicą znaną tylko Bobowi,
  • Alicja, chcąc wysłać wiadomość do Boba, używa znanego jej klucza publicznego \displaystyle i. Własności funkcji z wytrychem sprawiają, że odszyfrowanie wiadomości jest łatwe dla Boba, natomiast trudne dla osób trzecich nieznających klucza \displaystyle t.

Najbardziej znanym systemem kryptograficznym opartym na powyższej zasadzie jest system RSA. Pamiętajmy przy tym, że nie znamy formalnego dowodu, mówiącego, że RSA spełnia warunki określone w definicji funkcji z wytrychem.

Prześledźmy teraz, w jaki sposób zdefiniowane są \displaystyle f, \displaystyle h i \displaystyle G dla systemu RSA.

Zadaniem maszyny \displaystyle G jest wygenerowanie pary kluczy. W tym celu losuje ona dwie liczby pierwsze \displaystyle p i \displaystyle q, z których każda ma długość większą niż \displaystyle n / 2 (gdzie \displaystyle n to długość przekazywanych wiadomości). Następnie oblicza ona liczbę \displaystyle N = p \cdot q oraz wartość funkcji Eulera dla tej liczby: \displaystyle \phi(N) = (p-1)\cdot(q-1). W kolejnym kroku znajdywana jest dowolna liczba \displaystyle e z zakresu \displaystyle [2, N-2], względnie pierwsza z \displaystyle \phi(N). Dla liczby \displaystyle e znajdywana jest następnie liczba \displaystyle d z zakresu \displaystyle [2, N-2] taka, że

\displaystyle d \cdot e = 1 mod \phi(N).

Istnienie takiej liczby spowodowane jest faktem, że \displaystyle e i \displaystyle \phi(N) są względnie pierwsze; liczbę \displaystyle d można efektywnie obliczyć z użyciem uogólnionego algorytmu Euklidesa.

W tym momencie można już zdefiniować parę kluczy: kluczem publicznym jest para liczb \displaystyle e oraz \displaystyle N; kluczem prywatnym jest para liczb \displaystyle d oraz \displaystyle N. Szyfrowanie słowa \displaystyle x wygląda następująco:

\displaystyle f(\langle e, N \rangle, x) = x^e mod N,

przy czym wiadomość \displaystyle x traktujemy jako binarny zapis pewnej liczby naturalnej. Dekodowanie słowa \displaystyle y określone jest w praktycznie identyczny sposób:

\displaystyle h(\langle d, N \rangle, y) = y^d mod N.

Wystarczy teraz przypomnieć sobie, że iloczyn \displaystyle d \cdot e jest postaci \displaystyle k\cdot\phi(N) + 1, dla pewnej liczby całkowitej \displaystyle k. W związku z tym

\displaystyle h(\langle d, N \rangle, f(\langle e, N \rangle, x)) = (x^e)^d mod N =  x^{k\cdot\phi(N) + 1} mod N = x^{k\cdot\phi(N)}\cdot x mod N = x.

Widzimy zatem, że funkcja \displaystyle h poprawnie dekoduje słowa zaszyfrowane z użyciem funkcji \displaystyle f -- Bob będzie zatem w stanie odtworzyć wiadomość wysłaną przez Alicję.

Systemy dowodów interaktywnych

W ostatnim fragmencie niniejszego kursu zajmiemy się klasą złożoności, będącą uogólnieniem klas \displaystyle NP i \displaystyle BPP. W tym celu zdefiniujemy pojęcie systemu dowodów interaktywnych.

Definicja 2.1

Systemem dowodów interaktywnych nazywamy parę funkcji \displaystyle V oraz \displaystyle P o sygnaturach:

\displaystyle V: \Sigma^\star \times \Sigma^\star \times \Sigma^\star \rightarrow \Sigma^\star \cup \{ accept, reject \}\displaystyle P: \Sigma^\star \times \Sigma^\star\rightarrow \Sigma^\star

taką, że funkcja \displaystyle V jest obliczalna na maszynie Turinga.

Działanie systemu dowodów interaktywnych polega na wymianie komunikatów między funkcjami \displaystyle V i \displaystyle P, przy czym funkcja \displaystyle P (z angielskiego prover) stara się "przekonać" funkcję \displaystyle V (verifier) o tym, że słowo wejściowe należy do rozpatrywanego języka, natomiast ostateczna decyzja w tej sprawie należy do \displaystyle V.

Komunikacja odbywa się naprzemiennie: funkcja \displaystyle V generuje wiadomość, przekazywaną funkcji \displaystyle P jako argument; funkcja \displaystyle P z kolei generuje odpowiedź przekazywaną funkcji \displaystyle V w następnej iteracji. Taka komunikacja odbywa się do momentu zaakceptowania lub odrzucenia słowa wejściowego przez funkcję \displaystyle V. W każdym kroku obie funkcje mają do dyspozycji zarówno słowo wejściowe, jak również pełną historię przekazanych dotychczas wiadomości.

Określmy teraz, co dokładnie oznaczają argumenty funkcji \displaystyle V i \displaystyle P. Argumenty funkcji \displaystyle V będziemy oznaczać w następujący sposób:

\displaystyle V(w, r, m_1 \# m_2 \# \ldots \# m_i).

Mają one następujące znaczenie:

  • \displaystyle w to słowo wejściowe,
  • \displaystyle r jest losowym ciągiem bitów,
  • \displaystyle m_1 \# m_2 \# \ldots \# m_i to konkatenacja dotychczasowych wiadomości, które zostały przekazane w procesie komunikacji (wiadomości o indeksach nieparzystych są wynikami działania funkcji \displaystyle V, natomiast wiadomości o indeksach parzystych są wynikami działania funkcji \displaystyle P).

Zwróćmy uwagę, że \displaystyle V ma do dyspozycji losowe słowo \displaystyle r; w praktyce oznacza to, że o funkcji \displaystyle V będziemy myśleć jako o pewnej losowej maszynie Turinga.

Zakładamy, że zarówno \displaystyle w jak i \displaystyle r są stałe w kolejnych iteracjach; słowo \displaystyle r jest zatem losowane jednokrotnie, przed rozpoczęciem procesu komunikacji. Warto też zauważyć, że słowa \displaystyle w i \displaystyle r całkowicie determinują działanie systemu.

Argumenty funkcji \displaystyle P będziemy oznaczać następująco:

\displaystyle P(w, m_1 \# m_2 \# \ldots \# m_i).

Ich znaczenie jest identyczne jak w przypadku argumentów funkcji \displaystyle V, nie ma wśród nich jednak słowa losowego.

Możemy w tym momencie zdefiniować klasę \displaystyle IP:

Definicja 2.2

Niech \displaystyle L \subseteq \Sigma^\star. Mówimy, że \displaystyle L \in IP wtedy i tylko wtedy, gdy istnieje system dowodów interaktywnych \displaystyle (V, P) oraz wielomiany \displaystyle p(n) i \displaystyle q(n) takie, że dla każdego słowa wejściowego \displaystyle w oraz losowego słowa \displaystyle r o długości \displaystyle p(|x|):

  • system daje odpowiedź po co najwyżej \displaystyle p(|x|) krokach,
  • w każdej iteracji czas działania maszyny obliczającej funkcję \displaystyle V jest ograniczony od góry przez \displaystyle q(|x|),
  • długość każdej wiadomości \displaystyle m_i jest nie większa niż \displaystyle p(|x|),
  • jeżeli \displaystyle w \in L, to prawdopodobieństwo zaakceptowania słowa przez system wynosi co najmniej \displaystyle 2/3,
  • jeżeli \displaystyle w \notin L oraz \displaystyle \bar P jest dowolną funkcją o sygnaturze zgodnej z \displaystyle P, zwracającą wiadomości nie dłuższe niż \displaystyle p(|x|), to system \displaystyle (V, \bar P) spełnia powyższe założenia na ilość iteracji, czas działania i długość wiadomości oraz akceptuje słowo \displaystyle w z prawdopodobieństwem nie większym niż \displaystyle 1/3.

O systemie \displaystyle (V, P) mówimy, że rozpoznaje język \displaystyle L w czasie wielomianowym.

Innymi słowy, jeżeli słowo \displaystyle w należy do języka, to \displaystyle V z dużym prawdopodobieństwem da się przekonać o tej przynależności przez pewną ustaloną funkcję \displaystyle P. Jeżeli jednak \displaystyle w nie należy do \displaystyle L, to \displaystyle V nie da się oszukać żadnej funkcji \displaystyle \bar P ze zbyt dużym prawdopodobieństwem.

Uwaga 2.3

Zwróćmy jeszcze uwagę, że branie pod uwagę tylko takich funkcji \displaystyle \bar P, które nie zwracają zbyt długich słów, nie jest istotnym ograniczeniem; funkcja \displaystyle V może w każdym kroku sprawdzać, czy odpowiedź funkcji \displaystyle \bar P nie jest zbyt długa i jeśli tak, to odrzucać słowo. W dalszej części rozdziału będziemy zakładali takie właśnie zachowanie funkcji \displaystyle V.

Widzimy zatem, że funkcja \displaystyle V musi być zabezpieczona przed oszustwami; jeżeli \displaystyle V mogłaby zaufać funkcji \displaystyle P, to mogłaby rozwiązać każdy problem decyzyjny -- wystarczyłoby po prostu skorzystać z nieograniczonej mocy obliczeniowej \displaystyle P. W naszym przypadku jednak nie wystarczy, aby \displaystyle P tylko rozwiązała problem decyzyjny -- musi jeszcze przekonać \displaystyle V do swojego rozwiązania.

Przykład 2.4

Rozważmy problem \displaystyle NON-GRAPH-ISO. Jest on zdefiniowany następująco:

\displaystyle NON-GRAPH-ISO = \{ \langle G, H \rangle: grafy \displaystyle G i \displaystyle H nie są izomorficzne \displaystyle \}.

Łatwo sie przekonać, że problem izomorfizmu grafów jest w klasie \displaystyle NP -- wystarczy zgadnąć odpowiednią permutację wierzchołków, po czym zweryfikować ją w trywialny sposób. \displaystyle NON-GRAPH-ISO należy zatem do \displaystyle coNP. Nie jest jednak obecnie znana odpowiedź na pytanie o przynależność tego problemu do klasy \displaystyle NP. Pokażemy teraz, w jaki sposób można rozwiązać \displaystyle NON-GRAPH-ISO za pomocą systemów dowodów interaktywnych, pokazując przynależność tego problemu do klasy \displaystyle IP.

System działa w prosty sposób: W kolejnych iteracjach funkcja \displaystyle V wybiera losowo jeden z grafów, a następnie w losowy sposób permutuje jego wierzchołki. Taki graf jest przekazywany jako wiadomość do funkcji \displaystyle P. Zadaniem funkcji \displaystyle P jest rozpoznanie, który z wyjściowych grafów został wylosowany i przekształcony przez \displaystyle V.

Ćwiczenie 2.5

Zdefiniuj, w jakich przypadkach \displaystyle V powinien zaakceptować, a w jakich odrzucić wejściową parę grafów. Oblicz, ile iteracji jest potrzebnych, aby system rozpoznawał język \displaystyle NON-GRAPH-ISO w czasie wielomianowym zgodnie z wcześniejszą definicją.

Rozwiązanie

Zachowanie \displaystyle V powinno być następujące. Jeżeli \displaystyle P pomyli się w odpowiedzi, \displaystyle V powinno odrzucić parę grafów -- czyli stwierdzić, że są izomorficzne. \displaystyle V powinno zaakceptować grafy -- czyli stwierdzić, że nie są izomorficzne -- jeżeli \displaystyle P dwukrotnie poprawnie odgadnie, który graf został wylosowany przez \displaystyle V. Pokażemy teraz, że system ten rozpoznaje \displaystyle NON-GRAPH-ISO. Załóżmy, że grafy wejściowe nie są izomorficzne. W tym przypadku łatwo wskazać funkcję \displaystyle P, która zawsze będzie udzielała prawidłowej odpowiedzi; prawdopodobieństwo akceptacji wyniesie zatem \displaystyle 1. Pozostaje jeszcze tylko pokazać, że jeżeli grafy nie są izomorficzne, to \displaystyle V nie da się oszukać żadnej funkcji \displaystyle \bar P. Funkcja \displaystyle \bar P nie ma jednak żadnej możliwości sprawdzenia, który graf został wybrany. Niezależnie zatem jak się zachowa, prawdopodobieństwo udzielenia dwóch kolejnych poprawnych odpowiedzi będzie nie większe niż \displaystyle 1/4, co kończy dowód.

Ćwiczenie 2.6

Pokaż, że klasa \displaystyle BPP jest zawarta w klasie \displaystyle IP.

Rozwiązanie

Weźmy dowolny problem z klasy \displaystyle BPP oraz program dla probabilistycznej maszyny Turinga, rozwiązujący ten problem w czasie wielomianowym. Wystarczy teraz, by funkcja \displaystyle V po prostu wykonała ten program i udzieliła odpowiedzi bez angażowania \displaystyle P.

Ćwiczenie 2.7

Rozpatrzmy takie systemy dowodów interaktywnych, w których funkcje \displaystyle V nie zależą od argumentu \displaystyle r (słowa losowego). Jaką klasę języków rozpoznają takie systemy, przy założeniach o złożoności analogicznych jak w przypadku klasy \displaystyle IP?

Rozwiązanie

Zauważmy najpierw, że tak określone protokoły komunikacyjne są w pełni deterministyczne (w tym sensie, że pozbawione są losowości). Zatem dla ustalonego systemu \displaystyle (V, P) i ustalonego słowa wejściowego odpowiedź protokołu zawsze jest taka sama.

Łatwo się przekonać, że za pomocą opisanych powyżej systemów można rozpoznać dowolny język z klasy \displaystyle NP. Protokół wygląda w następujący sposób: dla zadanego

słowa wejściowego \displaystyle w funkcja \displaystyle P zwraca świadka jego przynależności do rozważanego języka. Funkcja \displaystyle V następnie weryfikuje świadka w sposób deterministyczny w czasie wielomianowym i na tej podstawie udziela odpowiedzi. Jest jasne, że w przypadku, gdy \displaystyle w należy do rozważanego języka, odpowiednia funkcja \displaystyle P jest w stanie przekonać \displaystyle V o tej przynależności -- ponieważ nie ma żadnych restrykcji na złożoność funkcji \displaystyle P, może ona po prostu rozważyć wszystkich możliwych kandydatów na świadków o pewnej ustalonej z góry długości. Ponadto jeśli \displaystyle w nie należy do rozważanego języka, to \displaystyle V jest w stanie wykryć każdą próbę oszustwa.

Pokażemy teraz, że każdy język rozpoznawalny przez systemy opisane w treści zadania należy do \displaystyle NP. Ustalmy zatem pewien język \displaystyle L i rozpoznający go system \displaystyle (V, P). Załóżmy bez straty ogólności, że system ten dla słowa wejściowego \displaystyle w wykonuje dokładnie \displaystyle p(|w|) kroków oraz że każda przekazywana wiadomość ma długość \displaystyle p(|w|). Zdefiniujmy teraz niedeterministyczną maszynę Turinga

\displaystyle M, rozpoznającą język \displaystyle L. Załóżmy, że maszyna oprócz taśmy roboczej ma też (początkowo pustą) taśmę służącą do przechowywania kolejnych komunikatów. Działanie maszyny \displaystyle M będzie podzielone na fazy; w fazach nieparzystych maszyna będzie symulować działanie funkcji \displaystyle V -- to znaczy \displaystyle M przeczyta historię wysłanych dotychczas wiadomości i słowo wejściowe, i na tej podstawie dopisze kolejną wiadomość. W fazach parzystych maszyna \displaystyle M w sposób niedeterministyczny wygeneruje wiadomość o długości \displaystyle p(|w|) i dopisze ją na taśmę. W przypadku, gdy \displaystyle w \in L łatwo wskazać ścieżkę postępowania dla tej maszyny, która doprowadzi do akceptacji; będzie to ścieżka, w której wygenerowane w fazach parzystych wiadomości pokrywają się z odpowiedziami udzielanymi przez funkcję \displaystyle P. Rozważmy teraz przypadek \displaystyle w \notin L. Załóżmy nie wprost, że istnieje taka ścieżka postępowania maszyny \displaystyle M, która doprowadzi do akceptacji tego słowa. W takim przypadku możemy jednak utworzyć funkcję \displaystyle \bar P, która będzie zwracała wiadomości wygenerowane w fazach parzystych postępowania maszyny \displaystyle M. W tym przypadku funkcja \displaystyle V da się oszukać funkcji \displaystyle \bar P dla słowa \displaystyle w z prawdopodobieństwem równym 1 -- a zatem system \displaystyle (V, P) nie będzie rozpoznawał języka \displaystyle L, co jest sprzeczne z założeniem.

Pokazaliśmy zatem, że protokoły zdefiniowane w treści ćwiczenia rozpoznają klasę języków \displaystyle NP.

Możemy w tym momencie przypuszczać, że klasa \displaystyle IP jest znacząco większa od klasy \displaystyle NP. Nie wiemy obecnie, czy przypuszczenie to jest prawdziwe; przemawia jednak za nim poniższe twierdzenie.

Twierdzenie 2.8

\displaystyle IP = PSPACE

Dowód

Pokażemy najpierw fakt \displaystyle IP \subseteq PSPACE. W tym celu wybierzemy dowolny problem z klasy \displaystyle IP i rozwiążemy go z użyciem wielomianowej ilości pamięci.

Załóżmy, że system \displaystyle (V, P') akceptuje wybrany język w czasie wielomianowym.

Ustalmy słowo \displaystyle w. Będziemy mówić, że ciąg wiadomości \displaystyle m_1\#m_2\#\ldots\#m_i jest zgodny ze słowem losowym \displaystyle r, jeżeli stanowi on historię wiadomości po \displaystyle i iteracjach pewnego systemu \displaystyle (V, P'') używającego słowa losowego \displaystyle r. Warto zauważyć, że ciąg wiadomości może być zgodny z wieloma słowami losowymi (na przykład ciąg pusty jest zgodny z każdym słowem losowym), a słowo losowe może być zgodne z różnymi ciągami wiadomości (w zależności od funkcji \displaystyle P'').

Zdefiniujmy teraz funkcję \displaystyle P w taki sposób, by miała ona następującą własność:

\displaystyle \forall_w Pr((V, P) akceptuje \displaystyle w) = max_{P''} Pr((V, P'') akceptuje \displaystyle w).

Funkcja \displaystyle P zatem dla każdego słowa wejściowego zachowuje się w najlepszy możliwy sposób. Jest ona dobrze zdefiniowana, gdyż dla każdego wejściowego słowa zbiór prawdopodobieństw jest skończony -- przy ustalonym słowie \displaystyle w wszystkie możliwe funkcje \displaystyle P'' można przypisać do skończonej liczby klas równoważności, w ramach których system \displaystyle (V, P) zachowuje się identycznie (pamiętajmy, że w całym procesie komunikacji funkcja \displaystyle V wykonuje co najwyżej skończoną, ustaloną dla danego słowa wejściowego liczbę kroków).

Jest jasne, że \displaystyle (V, P) również akceptuje wybrany język w czasie wielomianowym -- od tej pory będziemy się zatem zajmowali tym konkretnym systemem. Nasz algorytm będzie dla każdego słowa wejściowego wprost obliczał prawdopodobieństwo zaakceptowania go przez system \displaystyle (V, P); tym samym, w zależności od wyniku, będzie mógł określić, czy słowo wejściowe należy do języka. Dla uproszczenia założymy, że system \displaystyle (V, P) daje odpowiedzi po dokładnie \displaystyle p(|x|) krokach.

Zdefiniujmy teraz funkcję mierzącą prawdopodobieństwo akceptacji słowa przez system \displaystyle (V, P) przy ustalonej częściowej historii komunikacji:

\displaystyle N(m_1\#m_2\#\ldots\#m_i) = Pr(słowo \displaystyle w zostanie zaakceptowane pod warunkiem, że dotychczasowe komunikaty reprezentowane są przez \displaystyle m_1\#m_2\#\ldots\#m_i).

W przypadku, gdy nie ma słowa losowego zgodnego z \displaystyle m_1\#m_2\#\ldots\#m_i, funkcji \displaystyle N(m_1\#m_2\#\ldots\#m_i) nadajemy wartość \displaystyle 0. Łatwo jest obliczyć \displaystyle N(m_1\#m_2\#\ldots\#m_{p(|x|)}):

  • jeżeli \displaystyle m_{p(|x|)} = accept i \displaystyle m_1\#m_2 \#\ldots\#m_{p(|x|)} jest zgodne z pewnym słowem losowym, to

\displaystyle N(m_1\#m_2\#\ldots\#m_{p(|x|)}) = 1,

  • w przeciwnym przypadku

\displaystyle N(m_1\#m_2\#\ldots\#m_{p(|x|)}) = 0.

Do obliczania wartości \displaystyle N dla mniejszej ilości kroków, możemy posłużyć się następującym wzorem rekurencyjnym:

  • jeżeli \displaystyle i jest nieparzyste, to

\displaystyle N(m_1\#m_2\#\ldots\#m_i) = \max_{m_{i+1}} N(m_1\#m_2\#\ldots\#m_{i+1}),

  • jeżeli \displaystyle i jest parzyste, to

\displaystyle N(m_1\#m_2\#\ldots\#m_i) = \sum_{m_{i+1}} Pr(m_{i+1}|m_1\#m_2\#\ldots\#m_i) \cdot N(m_1\#m_2\#\ldots\#m_{i+1}).

Wzór ten jest konsekwencją zachowania \displaystyle P i \displaystyle V: \displaystyle P w każdym kroku maksymalizuje prawdopodobieństwo akceptacji, natomiast zachowanie \displaystyle V zależne jest od historii wiadomości i słowa losowego.

W tym momencie wystarczą dwa spostrzeżenia. Po pierwsze, \displaystyle N(\epsilon) jest poszukiwanym przez nas prawdopodobieństwem zaakceptowania przez system \displaystyle (V, P) słowa \displaystyle w. Po drugie, \displaystyle N(\epsilon) jest obliczalne w pamięci wielomianowej: każde rekurencyjne wywołanie funkcji \displaystyle N powoduje sekwencyjne rozważenie wszystkich możliwych odpowiedzi, których długość jest jednak ograniczona od góry przez \displaystyle p(|x|). Dodatkowo przy obliczeniach na poziomie zagłębienia \displaystyle p(|x|) należy rozważyć wszystkie możliwe słowa losowe i sprawdzić ich zgodność z aktualnie rozważanym ciągiem komunikatów. Wszystkie te operacje można wykonać z użyciem \displaystyle O(p(|x|)^2) komórek pamięci.

Pokazaliśmy zatem, że \displaystyle IP \subseteq PSPACE.

image:End_of_proof.gif

Dowód zawierania w drugą stronę odbywa się poprzez przedstawienie protokołu komunikacji dla problemu \displaystyle QSAT. Aby przybliżyć stosowaną w tym protokole technikę, zaprezentujemy najpierw dowód przynależności do klasy \displaystyle IP problemu \displaystyle \#SAT(D) będącego wersją decyzyjną problemu \displaystyle \#SAT:

Definicja 2.9

\displaystyle \#SAT(D) = \{ \langle \phi, k \rangle: liczba wartościowań spełniających dla formuły \displaystyle \phi jest nie mniejsza niż \displaystyle k \}.

W dowodzie posłużymy się techniką zwaną arytmetyzacją; formuły logiczne będziemy zastępować wielomianami w następujący sposób:

  • zmienne formuły stają się zmiennymi wielomianu,
  • wyrażenia typu \displaystyle \neg x zastępujemy przez \displaystyle (1-x),
  • wyrażenia typu \displaystyle \alpha \wedge \beta zastępujemy przez \displaystyle \alpha \cdot \beta,
  • wyrażenia typu \displaystyle \alpha \vee \beta zastępujemy przez \displaystyle (1 - (1 - \alpha)\cdot(1 - \beta)).

Dla uproszczenia założymy na razie, że wielomiany te określone są na liczbach rzeczywistych.

Ćwiczenie 2.10

Niech \displaystyle \phi będzie formułą z \displaystyle m zmiennymi, natomiast \displaystyle W(x_1, \ldots, x_m) wielomianem otrzymanych w sposób przedstawiony powyżej. Weźmy dowolne wartościowanie zmiennych formuły \displaystyle \phi i podstawmy je do wielomianu \displaystyle W (to znaczy podstawmy 0, gdy zmienna jest wartościowana na "fałsz" i 1 w przeciwnym przypadku). Pokaż, że wartość wielomianu \displaystyle W jest równa 1, gdy wybrane wartościowanie jest wartościowaniem spełniającym dla \displaystyle \phi oraz 0 w przeciwnym przypadku.

Wskazówka

Zastosuj indukcję matematyczną.

Rozwiązanie

Indukcja będzie zdefiniowana ze względu na ilość literałów w formule. Niech \displaystyle \phi będzie formułą z jednym literałem. Będzie ona zatem postaci \displaystyle \phi = x lub \displaystyle \phi = \neg x. Po zastosowaniu procesu arytmetyzacji wielomian będzie miał postać odpowiednio \displaystyle W(x) = x lub \displaystyle W(x) = (1 - x). Jest zatem jasne, że dla wartościowania zmiennej \displaystyle x na "fałsz" wartości wielomianów wynoszą odpowiednio 0 i 1, a przy wartościowaniu na "prawdę" odpowiednio 1 i 0 -- spełnione są zatem wymagania opisane w treści ćwiczenia.

Załóżmy teraz, że własność podana w treści jest spełniona dla wszystkich

formuł o długości nie większej niż \displaystyle n-1; pokażemy, że jest ona również spełniona dla formuł o długości \displaystyle n. Weźmy zatem formułę \displaystyle \phi o długości \displaystyle n i załóżmy, że \displaystyle \phi = \alpha \wedge \beta. Wielomian \displaystyle W jest zatem postaci \displaystyle W(x_1,\ldots,x_m) = W_\alpha(x_1,\ldots,x_m) * W_\beta(x_1,\ldots,x_m). Niech \displaystyle a_1,\ldots,a_m będzie wartościowaniem spełniającym dla formuły \displaystyle \phi; jest ono zatem wartościowaniem spełniającym dla \displaystyle \alpha i \displaystyle \beta. Formuły \displaystyle \alpha i \displaystyle \beta mają co najwyżej \displaystyle n-1 literałów -- korzystając z założenia indukcyjnego, możemy stwierdzić, że:

\displaystyle W_\alpha(a_1,\ldots,a_m) = W_\beta(a_1,\ldots,a_m) = 1.

W związku z tym:

\displaystyle W(a_1,\ldots,a_m) = 1.

Załóżmy teraz, że \displaystyle a_1,\ldots,a_m nie jest wartościowaniem spełniającym

dla \displaystyle \phi. Nie jest zatem wartościowaniem spełniającym dla przynajmniej jednej z formuł \displaystyle \alpha lub \displaystyle \beta. W związku z tym zachodzi własność:

\displaystyle W_\alpha(a_1,\ldots,a_m) = 0

lub

\displaystyle W_\beta(a_1,\ldots,a_m) = 0.

W konsekwencji:

\displaystyle W(a_1,\ldots,a_m) = 0.

Dowód przypadku, gdy \displaystyle \phi = \alpha \vee \beta, jest analogiczny.

Ćwiczenie 2.11

Niech \displaystyle n oznacza liczbę -- niekoniecznie różnych -- literałów (zmiennych i ich zaprzeczeń) w formule \displaystyle \phi. Pokaż, że stopień każdej zmiennej w wielomianie \displaystyle W jest nie większy niż \displaystyle n.

Rozwiązanie

Dowód znowu przebiega przez indukcję ze względu na ilość literałów w formule. Jeżeli formuła zawiera dokładnie jeden literał, to wielomian powstający w wyniku arytmetyzacji jest funkcją liniową. Stopień każdej zmiennej jest zatem równy 0 lub 1.

Załóżmy teraz, że własność podana w treści jest spełniona dla formuł o nie więcej niż

\displaystyle n-1 literałach; pokażemy, że jest ona też spełniona dla formuł o \displaystyle n literałach. Weźmy formułę \displaystyle \phi o \displaystyle n literałach i załóżmy, że jest ona postaci \displaystyle \phi = \alpha \wedge \beta. Oznaczmy długości formuł \displaystyle \alpha i \displaystyle \beta jako \displaystyle l_\alpha i \displaystyle l_\beta. Ustalmy też dowolną zmienną \displaystyle x_i występującą w formule \displaystyle \phi. Z założenia indukcyjnego wiemy, że stopień tej zmiennej w wielomianach \displaystyle W_\alpha i \displaystyle W_\beta jest co najwyżej równy odpowiednio \displaystyle l_\alpha lub \displaystyle l_\beta. Wielomian otrzymany z formuły \displaystyle \phi jest postaci \displaystyle W(x_1,\ldots,x_m) = W_\alpha(x_1,\ldots,x_m) * W_\beta(x_1,\ldots,x_m). Stopień \displaystyle W jako wielomianu zmiennej \displaystyle x_i jest zatem równy co najwyżej \displaystyle l_\alpha + l_\beta -- liczba ta jest równa ilości literałów w formule \displaystyle \phi.

W przypadku, gdy \displaystyle \phi = \alpha \vee \beta, wielomian \displaystyle W jest postaci:

\displaystyle W(\ldots) = 1 - (1 - W_\alpha(\ldots))\cdot(1 - W_\beta(\ldots)).

Po dokonaniu mnożenia otrzymamy:

\displaystyle W(\ldots) = W_\alpha (\ldots) + W_\beta (\ldots) - W_\alpha (\ldots) \cdot W_\beta(\ldots).

Jest zatem jasne, że stopień \displaystyle W jako zmiennej \displaystyle x_i jest nie większy niż

\displaystyle l_\alpha + l_\beta.

Zdefiniujmy teraz ciąg wielomianów \displaystyle f_0, f_1, \ldots, f_m w następujący sposób:

  • \displaystyle f_m jest wielomianem otrzymanym z formuły \displaystyle \phi w wyniku procesu arytmetyzacji,
  • \displaystyle f_i(x_1, x_2, \ldots, x_i) := f_{i+1}(x_1, x_2, \ldots, x_i, 0) + f_{i+1}(x_1, x_2, \ldots, x_i, 1).

Zauważmy, że ilość argumentów zmniejsza się w kolejnych funkcjach, a \displaystyle f_0 nie posiada żadnych argumentów (czyli jest stałą). Funkcje te spełniają następującą własność:

\displaystyle \forall_{a_1,a_2,\ldots,a_i \in \{0, 1\}} f_i(a_1, a_2, \ldots, a_i) = \sum_{x_{i+1} \in \{0, 1\}} \ldots \sum_{x_{m} \in \{0, 1\}} f_m(a_1,a_2, \ldots, a_i, x_{i+1}, \ldots, x_m)

Oznacza to, że jeżeli \displaystyle a_1, \ldots, a_i reprezentują pewne wartościowanie zmiennych \displaystyle x_1, \ldots, x_i, to \displaystyle f_i(a_1,\ldots,a_i) wyznacza liczbę wartościwoań spełniających formułę \displaystyle \phi rozpoczynających się od \displaystyle (a_1, \ldots, a_i). Oczywistym wnioskiem z powyższego spostrzeżenia jest to, że \displaystyle f_0() jest liczbą wszystkich wartościowań spełniających \displaystyle \phi.

Zauważmy jeszcze, że w wielomianach \displaystyle f_i zachowana jest własność, mówiąca że każda zmienna występuje co najwyżej w stopniu \displaystyle n. Ilość wyrazów występujących w tych wielomianach może być jednak wykładnicza ze względu na długość formuły; z tego powodu obliczanie tych wielomianów może być procesem czasochłonnym.

Przedstawiany protokół komunikacyjny obliczanie wielomianów \displaystyle f_0,\ldots,f_{m-1} zleca funkcji \displaystyle P. Ta następnie przekazuje funkcji \displaystyle V pewne informacje o wielomianach, na podstawie których \displaystyle V może z dużym prawdopodobieństwem rozstrzygnąć, czy \displaystyle f_0,\ldots,f_{m-1} zostały "uczciwie" obliczone zgodnie z powyższą rekurencyjną procedurą, czy też \displaystyle P próbuje oszukać \displaystyle V.

Protokół nie operuje na liczbach rzeczywistych -- zamiast nich używamy ciała \displaystyle {\mathbb Z}_p, gdzie \displaystyle p jest liczbą pierwszą większą niż \displaystyle 2^n. Wielomiany określone nad takim ciałem mają wiele cech wspólnych z wielomianami nad \displaystyle {\mathbb R} -- w szczególności wielomian jednej zmiennej o stopniu \displaystyle n, który nie jest stale równy 0, ma co najwyżej \displaystyle n pierwiastków. W rezultacie dwa różne wielomiany stopnia nie większego niż \displaystyle n mogą być równe w co najwyżej \displaystyle n punktach.

W tym momencie jesteśmy gotowi do przedstawienia protokołu dla \displaystyle \#SAT(D):

  • Krok 1 (P): Znajdź liczbę pierwszą \displaystyle p z przedziału \displaystyle [2^n, 2^{n+1}] oraz jej certyfikat pierwszości (taka liczba na pewno istnieje -- wynika to z twierdzenia Bertranda--Czebyszewa). Prześlij je jako wiadomość.
  • Krok 2 (V): Sprawdź poprawność liczby \displaystyle p, odrzuć słowo wejściowe, jeśli \displaystyle p lub jej certyfikat są nieprawidłowe.
  • Krok 3 (P): Oblicz \displaystyle f_0() i prześlij jako wiadomość.
  • Krok 4 (V): Sprawdź, czy \displaystyle f_0() \geq k -- jeśli nie to odrzuć słowo wejściowe.
  • Krok 5 (P): Oblicz \displaystyle f_1(z) (wielomian ze zmienną \displaystyle z) i prześlij jego współczynniki jako wiadomość.
  • Krok 6 (V): Sprawdź, czy \displaystyle f_0() = f_1(0) + f_1(1). Wylosuj dowolną liczbę \displaystyle r_1 z \displaystyle {\mathbb Z}_p i prześlij ją jako wiadomość,
  • Krok 7 (P): Oblicz \displaystyle f_2(r_1, z) (to też jest wielomian z jedną zmienną \displaystyle z) i prześlij jego współczynniki jako wiadomość.
  • Krok 8 (V): Sprawdź, czy \displaystyle f_1(r_1)=f_2(r_1,0)+f_2(r_1,1). Wylosuj dowolną liczbę \displaystyle r_2 z \displaystyle {\mathbb Z}_p i prześlij ją jako wiadomość.
  • \displaystyle \cdots
  • Krok \displaystyle 2m + 4 (V): Sprawdź, czy \displaystyle f_{m-1}(r_1, \ldots, r_{m-1})=f_m(r_1,\ldots,r_{m-1},0)+f_m(r_1,\ldots,r_{m-1},1). Sprawdź, czy \displaystyle f_m(r_1,\ldots,r_{m-1},z) jest wielomianem otrzymanym przez arytmetyzację formuły \displaystyle \phi i podstawienie \displaystyle r_1,\ldots,r_{m-1} jako pierwszych \displaystyle m-1 argumentów otrzymanego wielomianu. Jeżeli tak, to zaakceptuj słowo wejściowe, w przeciwnym przypadku odrzuć je.

W przypadku, gdy słowo wejściowe należy do \displaystyle \#SAT(D), jest jasne, że funkcja \displaystyle P, postępująca zgodnie z powyższym protokołem, zawsze przekona \displaystyle V o tej przynależności. Popatrzmy teraz, co się stanie, gdy słowo wejściowe nie należy do \displaystyle \#SAT(D); w tym przypadku wartość \displaystyle f_0() podana przez \displaystyle \bar P będzie musiała się różnić od wartości prawdziwej (oznaczmy ją jako \displaystyle \bar {f_0}()). W związku z tym przynajmniej jedna z wartości \displaystyle f_1(0) lub \displaystyle f_1(1) będzie różna od oczekiwanej -- \displaystyle \bar {f_1}(0) lub \displaystyle \bar {f_1}(1) -- a co za tym idzie wielomian \displaystyle f_1(z) będzie różny od \displaystyle \bar {f_1}(z). Pokażemy teraz fakt będący sednem naszego dowodu: jeżeli wielomian \displaystyle f_i(r_1,r_2,\ldots,r_{i-1},z) jest różny od wielomianu \displaystyle \bar {f_i}(r_1,r_2,\ldots,r_{i-1},z), to z dużym prawdopodobieństwem również \displaystyle f_{i+1}(r_1,r_2,\ldots,r_i,z) będzie różny od \displaystyle \bar {f_{i+1}}(r_1,r_2,\ldots,r_i,z). Zauważmy, że jesli \displaystyle r_i zostanie wylosowane w taki sposób, że \displaystyle f_i(r_1,\ldots,r_i)=\bar {f_i}(r_1,\ldots,r_i), to \displaystyle \bar P w kolejnym kroku będzie mógł zwrócić wielomian \displaystyle \bar {f_{i+1}} (r_1, \ldots,r_i,z) -- a zatem skutecznie oszuka \displaystyle V. Aby tak się jednak stało wylosowana wartość \displaystyle r_i musi być jednym z punktów, w których \displaystyle \bar {f_i}(r_1,r_2,\ldots,r_{i-1},z) i \displaystyle \bar {f_i}(r_1,r_2,\ldots,r_{i-1},z) są równe. Prawdopodobieństwo takiego zdarzenia to co najwyżej \displaystyle n/{2^n}. Jeżeli \displaystyle f_i(r_1,\ldots,r_i)\neq \bar {f_i}(r_1,\ldots,r_i), to niewątpliwie \displaystyle f_{i+1}(r_1,\ldots,r_i,0) \neq \bar {f_{i+1}}(r_1,\ldots,r_i,0) lub \displaystyle f_{i+1}(r_1,\ldots,r_i,1) \neq \bar {f_{i+1}}(r_1,\ldots,r_i,1) -- a co za tym idzie wielomian \displaystyle f_{i+1}(r_1,\ldots,r_i,z) będzie różny od wielomianu \displaystyle \bar {f_{i+1}}(r_1,\ldots,r_i,z).

Widzimy więc, że prawdopodobieństwo zdarzenia, w którym \displaystyle f_m(r_1,\ldots,r_{m-1},z) jest równy \displaystyle \bar {f_m}(r_1,\ldots,r_{m-1},z) jest ograniczone od góry przez wyrażenie \displaystyle m \cdot n / {2^n}, co z kolei jest nie większe niż \displaystyle n^2 / {2^n}. \displaystyle V jest w stanie wykryć niezgodność tych wielomianów w czasie wielomianowym w sposób deterministyczny -- a zatem \displaystyle n^2 / {2^n} jest górnym ograniczeniem na prawdopodobieństwo zaakceptowania przez \displaystyle V słowa spoza \displaystyle \#SAT(D).

W tym momencie wystarczy już tylko zauważyć, że \displaystyle n^2 / {2^n} jest mniejsze od \displaystyle 1/3 dla każdego \displaystyle n \geq 8; protokół będziemy zatem stosować dla formuł o co najmniej 8 literałach. Pozostałe mogą zostać stablicowane przez \displaystyle V i rozstrzygane w czasie stałym, bez angażowania \displaystyle P.

Powyższy protokół pokazuje zatem przynależność \displaystyle \#SAT(D) do klasy \displaystyle IP.

Powróćmy teraz do problemu \displaystyle QSAT. Możemy myśleć o kwantyfikatorach jako o pewnych transformacjach wykonywanych na zarytmetyzowanej formule logicznej, przedstawiając ten proces schematycznie jako:

\displaystyle {Q_1}_{x_1} {Q_2}_{x_2} \ldots {Q_m}_{x_m} \langle \phi \rangle,

gdzie \displaystyle Q_i \in \{ \exists, \forall \}, natomiast \displaystyle \langle \phi \rangle to formuła \displaystyle \phi przekształcona w procesie arytmetyzacji. Operacje \displaystyle Q_i definiujemy następująco:

  • \displaystyle {Q_i}_{x_i} W(x_1,x_2,\ldots,x_i,\ldots,x_m) = W(x_1,x_2,\ldots,0,\ldots,x_m) \cdot W(x_1,x_2,\ldots,1,\ldots,x_m) gdy \displaystyle Q_i = \forall,
  • \displaystyle {Q_i}_{x_i} W(x_1,x_2,\ldots,x_i,\ldots,x_m) = 1 - (1 - W(x_1,x_2,\ldots,0,\ldots,x_m)) \cdot (1 - W(x_1,x_2,\ldots,1,\ldots,x_m)), \mbox{ gdy }\displaystyle Q_i = \exists.

Możemy w tym momencie spróbować powtórzyć poprzedni dowód, to znaczy zdefiniować ciąg wielomianów \displaystyle f_0,f_1,\ldots,f_m tak, aby \displaystyle f_m był zarytmetyzowaną formułą \displaystyle \phi, a \displaystyle f_{i-1} = {Q_i}_{x_i} f_i. Niestety w tym przypadku wielomiany w kolejnych krokach są mnożone, a nie dodawane -- w związku z tym stopnie zmiennych w kolejnych wielomianach mogą rosnąć eksponencjalnie; nie będziemy zatem w stanie wypisać współczynników nawet po zawężeniu do jednej zmiennej.

Aby temu zaradzić, będziemy "po drodze" przekształcać wielomiany z użyciem następującej operacji:

\displaystyle R_{x_i} W(x_1,x_2,\ldots,x_i,\ldots,x_m) = x_i \cdot W(x_1,x_2,\ldots,1,\ldots,x_m) + (1 - x_i) \cdot W(x_1,x_2,\ldots,0,\ldots,x_m).

Wielomian otrzymany w wyniku takiej transformacji ma następujące cechy:

  • jest liniowy ze względu na \displaystyle x_i,
  • maksymalne stopnie pozostałych zmiennych pozostają takie same,
  • nowy wielomian daje takie same wyniki co wyjściowy dla argumentów Boole'owskich (to znaczy dla liczb 0 i 1).

Zmodyfikowana procedura postępowania będzie wyglądała następująco:

\displaystyle {Q_1}_{x_1} R_{x_1} {Q_2}_{x_2} R_{x_1} R_{x_2} {Q_3}_{x_3} \ldots {Q_m}_{x_m} R_{x_1} \ldots R_{x_m} \langle \phi \rangle.

Zauważmy, że \displaystyle R nie zmienia ilości zmiennych wielomianu, natomiast operacje \displaystyle Q_i zmniejszają tę liczbę o 1. Liczbę transformacji oznaczymy jako \displaystyle k -- będzie ona kwadratowo zależna od liczby zmiennych \displaystyle m. W tym momencie możemy już zdefiniować ciąg wielomianów \displaystyle f_0,f_1,\ldots,f_k: \displaystyle f_k będzie zarytmetyzowaną formułą \displaystyle \phi, natomiast \displaystyle f_{i-1} będzie otrzymywany z \displaystyle f_i za pomocą odpowiedniej transformacji \displaystyle Q_j lub \displaystyle R. Ze względu na stosowanie \displaystyle R stopień każdej zmiennej w tych wielomianach jest ograniczony przez liczbę literałów w \displaystyle \phi (oznaczaną ponownie jako \displaystyle n). Podobnie jak wcześniej, \displaystyle f_0() będzie szukanym przez nas wynikiem; wielomiany ponownie będą określone nad pewnym skończonym ciałem \displaystyle {\mathbb Z}_p -- tym razem jednak wystarczy nam dowolna liczba pierwsza \displaystyle p większa niż \displaystyle n^4. Taką liczbę \displaystyle V może znaleźć samodzielnie, dla uproszczenia jednak założymy, że otrzymana zostanie ona tak samo jak \displaystyle p w protokole dla \displaystyle \#SAT(D). Właściwy protokół będzie oparty na tej samej zasadzie co poprzednio: \displaystyle P wypisze wartość \displaystyle f_0(), po czym będzie wypisywała pewne zawężenia wielomianów \displaystyle f_1, \ldots, f_k; \displaystyle V będzie sprawdzała, czy kolejne wielomiany nie są sprzeczne z poprzednimi (czyli również z \displaystyle f_0), a na końcu samodzielnie obliczy zawężenie wielomianu \displaystyle \bar {f_k} i porówna je z wielomianem otrzymanym od \displaystyle P. Ponownie, jeśli \displaystyle P skłamie przy podawaniu wartości \displaystyle f_0(), prawdopodobieństwo tego, że uda jej się to kłamstwo zamaskować, będzie nieduże. Popatrzmy teraz jak wygląda pojedynczy krok protokołu. W tym celu oznaczmy \displaystyle i-tą transformację jako \displaystyle {S_i}_{y_i}. Załóżmy bez utraty ogólności, że \displaystyle {y_i} = x_1, natomiast \displaystyle y_{i-1} = x_2 -- założenie to ma na celu jedynie uproszczenie indeksowania. Podobnie jak w przypadku \displaystyle \#SAT(D)\displaystyle V dysponuje współczynnikami \displaystyle f_{i-1} jako wielomianu zmiennej \displaystyle {x_2}, gdzie za pozostałe zmienne zostały podstawione pewne wylosowane uprzednio stałe. Jeżeli operacja \displaystyle S_i jest kwantyfikatorem, to protokół zachowuje się praktycznie identycznie jak w poprzednim dowodzie; w tym przypadku \displaystyle V ma do dyspozycji wielomian \displaystyle f_{i-1}(x_2,r_3,r_4,\ldots,r_s), losuje liczbę \displaystyle r_2 i prosi \displaystyle P o przesłanie współczynników \displaystyle f_i(x_1,r_2,\ldots,r_s). Jeżeli wielomian \displaystyle f_{i-1}(x_2,r_3,r_4,\ldots,r_s) nie jest prawidłowy -- czyli gdy funkcja \displaystyle P próbuje oszukać \displaystyle V i nie udało jej się jeszcze "zatrzeć śladów oszustwa" -- to prawdopodobieństwo, że wielomian \displaystyle f_i(x_1,r_2,\ldots,r_s) będzie prawidłowy, wyniesie co najwyżej \displaystyle n/{n^4}, czyli \displaystyle 1/{n^3}. Rozpatrzmy teraz przypadek, gdy \displaystyle S_i = R. \displaystyle V ma do dyspozycji wielomian \displaystyle f_{i-1}(r_1,x_2,r_3,\ldots,r_s). W pierwszej kolejności \displaystyle V losuje pewną liczbę \displaystyle {r'}_2, po czym prosi \displaystyle P o przesłanie współczynników wielomianu \displaystyle f_{i-1}(x_1,{r'}_2,r_3,\ldots,r_s). Następnie \displaystyle V sprawdza, czy podstawienie \displaystyle {r'}_2 do pierwszego z tych wielomianów daje ten sam wynik, co podstawienie \displaystyle r_1 do drugiego. Ponownie argumentujemy, że jeśli wielomian \displaystyle f_{i-1}(r_1,x_2,r_3,\ldots,r_s) był nieprawidłowy -- czyli różny od "wzorcowego" wielomianu \displaystyle \bar {f_{i-1}}(r_1,x_2,r_3,\ldots,r_s) -- to prawdopodobieństwo, że dla wylosowanej wartości \displaystyle {r'}_2 zachodzi \displaystyle f_{i-1}(r_1,{r'}_2,r_3,\ldots,r_s) = \bar {f_{i-1}}(r_1,{r'}_2,r_3,\ldots,r_s) jest nie większe niż \displaystyle 1/{n^3}. W związku z tym wielomian \displaystyle f_{i-1}(x_1,{r'}_2,r_3,\ldots,r_s) będzie poprawny z prawdopodobieństwem co najwyżej równym \displaystyle 1/{n^3}. W następnym kroku \displaystyle P przesyła współczynniki wielomianu \displaystyle f_i(x_1,{r'}_2,r_3,\ldots,r_s). Zauważmy, że \displaystyle V jest w stanie samodzielnie sprawdzić, czy wielomian \displaystyle f_{i-1}(x_1,{r'}_2,r_3,\ldots,r_s) został otrzymany z \displaystyle f_i(x_1,{r'}_2,r_3,\ldots,r_s) w wyniku transformacji \displaystyle R -- transformacja ta jest przecież jednoznacznie określona. Jeżeli założymy zatem, że wielomian \displaystyle f_{i-1}(x_1,{r'}_2,r_3,\ldots,r_s) jest nieprawidłowy, to nieprawidłowy musi być też wielomian \displaystyle f_i(x_1,{r'}_2,r_3,\ldots,r_s). Reasumując -- prawdopodobieństwo, że w kroku odpowiadającym pewnej transformacji \displaystyle R funkcji \displaystyle V uda się skutecznie "zatrzeć ślad" po wcześniejszym oszustwie, jest nie większe niż \displaystyle 1/{n^3}.

Uwaga 2.12

Zauważmy, że w trakcie działania protokołu losujemy \displaystyle k liczb; jest zatem możliwe (i pewne), że w tym procesie \displaystyle V będzie podstawiać w miejsce tej samej zmiennej różne wylosowane liczby. Dla przykładu -- powyżej wylosowaliśmy liczbę \displaystyle {r'}_2; być może jednak już wcześniej dokonywaliśmy innej operacji na zmiennej \displaystyle x_2 i wylosowaliśmy inną liczbę \displaystyle r_2. Widzimy zatem, że pewne wylosowane wartości zostają w tym procesie "zapomniane" i na ich miejsce losowane są nowe. Oczywiście wyniki nowych losowań powinny być niezależne od poprzednich -- inaczej \displaystyle P mógłby osiągnąć większe prawdopodobieństwo skutecznego oszukania \displaystyle V.

Jak zauważyliśmy wcześniej, liczba wykonywanych transformacji \displaystyle k jest kwadratowo zależna od \displaystyle m; w szczególności natychmiastowe jest oszacowanie \displaystyle k < (m+1)^2. W związku z tym prawdopodobieństwo, że \displaystyle V zaakceptuje słowo wejściowe nienależące do \displaystyle QSAT jest nie większe niż \displaystyle (m+1)^2/{n^3}, co z kolei jest nie większe niż \displaystyle (n+1)^2/{n^3} = O(1/n). Ponownie zatem \displaystyle V musi "stablicować" wyniki dla pewnej skończonej liczby formuł (w tym przypadku stablicowane muszą zostać formuły o co najwyżej 4 literałach), a dla reszty protokół będzie dawał prawidłowe wyniki z wymaganym prawdopodobieństwem.

Powyższy protokół pokazuje więc przynależność \displaystyle QSAT do klasy \displaystyle IP. W tym momencie wystarczy zauważyć, że klasa \displaystyle IP jest domknięta ze względu na redukcje wielomianowe; jeśli \displaystyle L_1 redukuje się do \displaystyle L_2 oraz znamy protokół rozwiązujący \displaystyle L_2, to \displaystyle V może w pierwszym kroku dokonać redukcji, po czym postępować zgodnie z protokołem dla \displaystyle L_2. Korzystając z faktu, że \displaystyle QSAT jest problemem \displaystyle PSPACE-zupełnym, stwierdzamy, że każdy problem z klasy \displaystyle PSPACE zawarty jest w klasie \displaystyle IP.

Ćwiczenie 2.13

Wyjaśnij, czemu w protokole \displaystyle \#SAT(D) potrzebowaliśmy ciała o co najmniej \displaystyle 2^n elementach.

Rozwiązanie

Widzimy, że aby spełnić wymagania dotyczące prawdopodobieństwa zaakceptowania słowa spoza języka, wystarczy ciało o wielkości \displaystyle n^3. W przypadku \displaystyle \#SAT(D) ciało \displaystyle {\mathbb Z}_p służy nam jednak nie tylko jako dostarczyciel dużej przestrzeni prawdopodobieństwa, lecz również do zliczania ilości spełniających wartościowań dla zadanej formuły logicznej. Z tego powodu potrzebujemy co najmniej \displaystyle 2^m liczb -- co oznacza, że w zdegenerowanym przypadku, gdy każda zmienna jest używana w dokładnie jednym literale wymagane ciało musi mieć liczność nie mniejszą niż \displaystyle 2^n.

Testy końcowe