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

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 $f:\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$. Mówimy, że $f$ jest funkcją jednokierunkową wtedy i tylko wtedy, gdy:

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

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

Ćwiczenie 1.2

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

Rozwiązanie

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

Z drugiej strony nierówność $P\ne 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 $x$ istnieje co najwyżej jedna akceptująca ścieżka obliczeń.

Definicja 1.4

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

Uwaga 1.5

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

$L\in UP⟺{\mathrm{\exists }}_{p(x)-wielomian}{\mathrm{\exists }}_{L^{\prime }\in P}{\mathrm{\forall }}_{n\in \mathbb{\mathbb{N}}}{\mathrm{\forall }}_{w\in \{0,1{\}}^n}[w\in L\Rightarrow ({\mathrm{\exists }!}_{v\in \{0,1{\}}^{p(n)}}⟨w,v⟩\in L^{\prime })]\wedge [w\notin L\Rightarrow (\mathrm{\neg }{\mathrm{\exists }}_{v\in \{0,1{\}}^{p(n)}}⟨w,v⟩\in L^{\prime })]$.

W językach z klasy $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 $NP$.

Jest jasne, że $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ą $UP$ a funkcjami jednokierunkowymi.

Twierdzenie 1.6

Funkcje jednokierunkowe istnieją wtedy i tylko wtedy, gdy $UP\ne P$.

Dowód

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

$L_f=\{(x,y):{\mathrm{\exists }}_{z}f(z)=y\wedge z\le x\}$,

przy czym mówimy, że $z\le x$ wtedy i tylko wtedy, gdy

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

Łatwo można zauważyć, że $L_f\in UP$ - maszyna rozwiązująca ten problem najpierw "zgaduje" słowo $z$ o wielkości nie większej niż $|y{|}^k$, po czym sprawdza, czy w ustalonym porządku występuje ono nie później niż $x$ i czy zachodzi $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 $L_f\notin P$. Załóżmy zatem nie wprost, że istnieje jakiś wielomianowy algorytm rozwiązujący $L_f$. Wykorzystamy go teraz do obliczenia odwrotności funkcji $f$ w czasie wielomianowym. W pierwszym kroku zapytamy algorytm, czy $(1^{|y{|}^k},y)\in L_f$ (przez $1^{|y{|}^k}$ oznaczamy tutaj ciąg $|y{|}^k$ symboli $1$) - jeżeli otrzymamy odpowiedź NIE, to korzystając z definicji funkcji jednokierunkowej, możemy od razu stwierdzić, że nie istnieje słowo $x$ takie, że $f(x)=y$. Jeżeli otrzymamy odpowiedź TAK, to z użyciem co najwyżej $|y{|}^k-1$ zapytań do naszego algorytmu jesteśmy w stanie ustalić długość szukanego słowa $x$ (pytamy kolejno o $(1^{|y{|}^k-1},y)$, $(1^{|y{|}^k-2},y)$, itd., aż do momentu, gdy uzyskamy odpowiedź NIE). Gdy znamy już długość słowa $x$ pozostaje nam tylko obliczyć kolejne jego bity. Pierwszy bit otrzymamy, pytając o parę $(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 $(001^{|x|-2},y)$ lub $(101^{|x|-2},y)$. Kolejne bity odgadujemy w analogiczny sposób -- łącznie zatem wykonamy algorytm dla $L_{f}O(|y{|}^k)$ razy. W ten sposób uzyskamy deterministycznty algorytm odwracający funkcję $f$ w czasie wielomianowym.

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

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

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

$f_U(w)=1y$,

• w przeciwnym przypadku

$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 $y$ nie może być nadmiernie długi (bo jego długość jest wielomianowo zależna od długości $y$), a zatem $f_U$ nie może nadmiernie "skracać" słów. Funkcja $f_U$ jest też obliczalna w czasie wielomianowym -- wystarczy deterministycznie zweryfikować świadka, tak jak zrobiłaby to maszyna $U$. Pozostaje nam zatem tylko pokazanie, że funkcja odwrotna do $d$ nie jest obliczalna w czasie wielomianowym. Gdyby tak jednak było, to moglibyśmy rozpoznawać język $L$ w czasie wielomianowym: aby sprawdzić, czy $y\in L$ wystarczy zastosować odwrotność funkcji $f_U$ do słowa $1y$; jeżeli $y\notin L$, to dostaniemy odpowiedź mówiącą, że $1y$ nie można odwrócić; w przeciwnym przypadku otrzymamy świadka przynależności $y$ do języka $L$.

Na dzień dzisiejszy nie znamy oczywiście funkcji, o której wiedzielibyśmy, że jest jednokierunkowa; istnienie takiej funkcji natychmiastowo implikuje przecież nierówność $P\ne 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 $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 $w=⟨p,C(p),q,C(q)⟩$, gdzie $p<q$ a $C(p)$ i $C(q)$ są certyfikatami pierwszości odpowiednio dla $p$ i $q$, to

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

• w przeciwnym przypadku

$f_{MUL}(w)=0w$.

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. $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 $w$ postaci $⟨p,C(p),r,x⟩$, gdzie $p$ jest liczbą pierwszą, $C(p)$ certyfikatem jej pierwszości, $r$ jest najmniejszym generatorem grupy cyklicznej ${\mathbb{\mathbb{Z}}}_p^{\star }$, a $x$ jest liczbą naturalną z zakresu $[1,p-1]$

$f_{EXP}(w)=1⟨p,r,r^{x}modp)⟩$

• dla pozostałych $w$

$f_{EXP}(w)=0w$.

W tym przypadku, aby odwrócić funkcję $f_{EXP}$, musielibyśmy na podstawie liczb $p$, $r$ i $r^{x}modp$ umieć obliczyć wartość $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 $f:\{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$. Mówimy, że $f$ jest funkcją jednokierunkową wtedy i tylko wtedy, gdy:

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

$Pr[E(f(x))=x]\le 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ść $ϵ$, którą możemy traktować jako odpowiedź mówiącą, że wejście jest nieprawidłowe; dla przykładu przy adaptowaniu funkcji $f_{MUL}$ do powyższej definicji, w przypadku gdy $p$ lub $q$ nie będą liczbami pierwszymi lub gdy $C(p)$, lub $C(q)$ nie będą odpowiednimi certyfikatami, funkcja zwróci wartość $ϵ$. Zauważmy, że w powyższej definicji interesuje nas tylko trudność odszyfrowania wartości funkcji dla poprawnych wejść -- to znaczy w przypadku $f_{MUL}$ dla par liczb, które są pierwsze i których pierwszość jest potwierdzana przez $C(p)$ i $C(q)$. Funkcje $f_{MUL}$ jak i $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 $x$ do funkcji $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 $f:\{0,1{\}}^{\star }\times \{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$. Mówimy, że $f$ jest funkcją z wytrychem wtedy i tylko wtedy gdy istnieje losowa maszyna Turinga $G$ oraz funkcja $h:\{0,1{\}}^{\star }\times \{0,1{\}}^{\star }\to \{0,1{\}}^{\star }$ taka, że:

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

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

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

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

• dla każdego $n$, każdego słowa $x$ nie dłuższego niż $n$ i każdej pary $⟨i,t⟩$ mogącej być wynikiem działania maszyny $G$, dla słowa wejściowego $1^{n}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 ($n$) oraz parametr wyznaczający prawdopodobieństwo odszyfrowania pojedynczej wiadomości ($k$),
• Bob uruchamia maszynę $G$ i otrzymuje parę słów $⟨i,t⟩$. Słowo $i$ staje się dostępnym dla wszystkich kluczem publicznym, natomiast $t$ pozostaje tajemnicą znaną tylko Bobowi,
• Alicja, chcąc wysłać wiadomość do Boba, używa znanego jej klucza publicznego $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 $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ą $f$, $h$ i $G$ dla systemu RSA.

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

$d\cdot e=1mod\varphi (N)$.

Istnienie takiej liczby spowodowane jest faktem, że $e$ i $\varphi (N)$ są względnie pierwsze; liczbę $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 $e$ oraz $N$; kluczem prywatnym jest para liczb $d$ oraz $N$. Szyfrowanie słowa $x$ wygląda następująco:

$f(⟨e,N⟩,x)=x^{e}modN$,

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

$h(⟨d,N⟩,y)=y^{d}modN$.

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

$h(⟨d,N⟩,f(⟨e,N⟩,x))=(x^e{)}^{d}modN=x^{k\cdot \varphi (N)+1}modN=x^{k\cdot \varphi (N)}\cdot xmodN=x$.

Widzimy zatem, że funkcja $h$ poprawnie dekoduje słowa zaszyfrowane z użyciem funkcji $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 $NP$ i $BPP$. W tym celu zdefiniujemy pojęcie systemu dowodów interaktywnych.

Definicja 2.1

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

$V:{\mathrm{\Sigma }}^{\star }\times {\mathrm{\Sigma }}^{\star }\times {\mathrm{\Sigma }}^{\star }\to {\mathrm{\Sigma }}^{\star }\cup \{accept,reject\}P:{\mathrm{\Sigma }}^{\star }\times {\mathrm{\Sigma }}^{\star }\to {\mathrm{\Sigma }}^{\star }$

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

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

Komunikacja odbywa się naprzemiennie: funkcja $V$ generuje wiadomość, przekazywaną funkcji $P$ jako argument; funkcja $P$ z kolei generuje odpowiedź przekazywaną funkcji $V$ w następnej iteracji. Taka komunikacja odbywa się do momentu zaakceptowania lub odrzucenia słowa wejściowego przez funkcję $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 $V$ i $P$. Argumenty funkcji $V$ będziemy oznaczać w następujący sposób:

$V(w,r,m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)$.

Mają one następujące znaczenie:

• $w$ to słowo wejściowe,
• $r$ jest losowym ciągiem bitów,
• $m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{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 $V$, natomiast wiadomości o indeksach parzystych są wynikami działania funkcji $P$).

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

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

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

$P(w,m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)$.

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

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

Definicja 2.2

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

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

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

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

Uwaga 2.3

Zwróćmy jeszcze uwagę, że branie pod uwagę tylko takich funkcji $\overline{P}$, które nie zwracają zbyt długich słów, nie jest istotnym ograniczeniem; funkcja $V$ może w każdym kroku sprawdzać, czy odpowiedź funkcji $\overline{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 $V$.

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

Przykład 2.4

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

$NON-GRAPH-ISO=\{⟨G,H⟩:$ grafy $G$ i $H$ nie są izomorficzne $\}$.

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

System działa w prosty sposób: W kolejnych iteracjach funkcja $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 $P$. Zadaniem funkcji $P$ jest rozpoznanie, który z wyjściowych grafów został wylosowany i przekształcony przez $V$.

Ćwiczenie 2.5

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

Rozwiązanie

Zachowanie $V$ powinno być następujące. Jeżeli $P$ pomyli się w odpowiedzi, $V$ powinno odrzucić parę grafów -- czyli stwierdzić, że są izomorficzne. $V$ powinno zaakceptować grafy -- czyli stwierdzić, że nie są izomorficzne -- jeżeli $P$ dwukrotnie poprawnie odgadnie, który graf został wylosowany przez $V$. Pokażemy teraz, że system ten rozpoznaje $NON-GRAPH-ISO$. Załóżmy, że grafy wejściowe nie są izomorficzne. W tym przypadku łatwo wskazać funkcję $P$, która zawsze będzie udzielała prawidłowej odpowiedzi; prawdopodobieństwo akceptacji wyniesie zatem $1$. Pozostaje jeszcze tylko pokazać, że jeżeli grafy nie są izomorficzne, to $V$ nie da się oszukać żadnej funkcji $\overline{P}$. Funkcja $\overline{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ż $1/4$, co kończy dowód.

Ćwiczenie 2.6

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

Rozwiązanie

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

Ćwiczenie 2.7

Rozpatrzmy takie systemy dowodów interaktywnych, w których funkcje $V$ nie zależą od argumentu $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 $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 $(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 $NP$. Protokół wygląda w następujący sposób: dla zadanego słowa wejściowego $w$ funkcja $P$ zwraca świadka jego przynależności do rozważanego języka. Funkcja $V$ następnie weryfikuje świadka w sposób deterministyczny w czasie wielomianowym i na tej podstawie udziela odpowiedzi. Jest jasne, że w przypadku, gdy $w$ należy do rozważanego języka, odpowiednia funkcja $P$ jest w stanie przekonać $V$ o tej przynależności -- ponieważ nie ma żadnych restrykcji na złożoność funkcji $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 $w$ nie należy do rozważanego języka, to $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 $NP$. Ustalmy zatem pewien język $L$ i rozpoznający go system $(V,P)$. Załóżmy bez straty ogólności, że system ten dla słowa wejściowego $w$ wykonuje dokładnie $p(|w|)$ kroków oraz że każda przekazywana wiadomość ma długość $p(|w|)$. Zdefiniujmy teraz niedeterministyczną maszynę Turinga $M$, rozpoznającą język $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 $M$ będzie podzielone na fazy; w fazach nieparzystych maszyna będzie symulować działanie funkcji $V$ -- to znaczy $M$ przeczyta historię wysłanych dotychczas wiadomości i słowo wejściowe, i na tej podstawie dopisze kolejną wiadomość. W fazach parzystych maszyna $M$ w sposób niedeterministyczny wygeneruje wiadomość o długości $p(|w|)$ i dopisze ją na taśmę. W przypadku, gdy $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ę $P$. Rozważmy teraz przypadek $w\notin L$. Załóżmy nie wprost, że istnieje taka ścieżka postępowania maszyny $M$, która doprowadzi do akceptacji tego słowa. W takim przypadku możemy jednak utworzyć funkcję $\overline{P}$, która będzie zwracała wiadomości wygenerowane w fazach parzystych postępowania maszyny $M$. W tym przypadku funkcja $V$ da się oszukać funkcji $\overline{P}$ dla słowa $w$ z prawdopodobieństwem równym 1 -- a zatem system $(V,P)$ nie będzie rozpoznawał języka $L$, co jest sprzeczne z założeniem.

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

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

Twierdzenie 2.8

$IP=PSPACE$

Dowód

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

Załóżmy, że system $(V,P^{\prime })$ akceptuje wybrany język w czasie wielomianowym.

Ustalmy słowo $w$. Będziemy mówić, że ciąg wiadomości $m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i$ jest zgodny ze słowem losowym $r$, jeżeli stanowi on historię wiadomości po $i$ iteracjach pewnego systemu $(V,P^{″})$ używającego słowa losowego $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 $P^{″}$).

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

${\mathrm{\forall }}_{w}Pr((V,P)$ akceptuje $w)=ma{x}_{P^{″}}Pr((V,P^{″})$ akceptuje $w)$.

Funkcja $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 $w$ wszystkie możliwe funkcje $P^{″}$ można przypisać do skończonej liczby klas równoważności, w ramach których system $(V,P)$ zachowuje się identycznie (pamiętajmy, że w całym procesie komunikacji funkcja $V$ wykonuje co najwyżej skończoną, ustaloną dla danego słowa wejściowego liczbę kroków).

Jest jasne, że $(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 $(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 $(V,P)$ daje odpowiedzi po dokładnie $p(|x|)$ krokach.

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

$N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)=Pr($słowo $w$ zostanie zaakceptowane pod warunkiem, że dotychczasowe komunikaty reprezentowane są przez $m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)$.

W przypadku, gdy nie ma słowa losowego zgodnego z $m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i$, funkcji $N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)$ nadajemy wartość $0$. Łatwo jest obliczyć $N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_{p(|x|)})$:

• jeżeli $m_{p(|x|)}=accept$ i $m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_{p(|x|)}$ jest zgodne z pewnym słowem losowym, to

$N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_{p(|x|)})=1$,

• w przeciwnym przypadku

$N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_{p(|x|)})=0$.

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

• jeżeli $i$ jest nieparzyste, to

$N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)=\underset{m_{i+1}}{\max }N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_{i+1})$,

• jeżeli $i$ jest parzyste, to

$N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)=\sum _{m_{i+1}}Pr(m_{i+1}|m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_i)\cdot N(m_1\mathrm{\#}{m}_2\mathrm{\#}\dots \mathrm{\#}{m}_{i+1})$.

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

W tym momencie wystarczą dwa spostrzeżenia. Po pierwsze, $N(ϵ)$ jest poszukiwanym przez nas prawdopodobieństwem zaakceptowania przez system $(V,P)$ słowa $w$. Po drugie, $N(ϵ)$ jest obliczalne w pamięci wielomianowej: każde rekurencyjne wywołanie funkcji $N$ powoduje sekwencyjne rozważenie wszystkich możliwych odpowiedzi, których długość jest jednak ograniczona od góry przez $p(|x|)$. Dodatkowo przy obliczeniach na poziomie zagłębienia $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 $O(p(|x|{)}^2)$ komórek pamięci.

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

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

Definicja 2.9

$\mathrm{\#}SAT(D)=\{⟨\varphi ,k⟩:$ liczba wartościowań spełniających dla formuły $\varphi$ jest nie mniejsza niż $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 $\mathrm{\neg }x$ zastępujemy przez $(1-x)$,
• wyrażenia typu $\alpha \wedge \beta$ zastępujemy przez $\alpha \cdot \beta$,
• wyrażenia typu $\alpha \vee \beta$ zastępujemy przez $(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 $\varphi$ będzie formułą z $m$ zmiennymi, natomiast $W(x_1,\dots ,x_m)$ wielomianem otrzymanych w sposób przedstawiony powyżej. Weźmy dowolne wartościowanie zmiennych formuły $\varphi$ i podstawmy je do wielomianu $W$ (to znaczy podstawmy 0, gdy zmienna jest wartościowana na "fałsz" i 1 w przeciwnym przypadku). Pokaż, że wartość wielomianu $W$ jest równa 1, gdy wybrane wartościowanie jest wartościowaniem spełniającym dla $\varphi$ 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 $\varphi$ będzie formułą z jednym literałem. Będzie ona zatem postaci $\varphi =x$ lub $\varphi =\mathrm{\neg }x$. Po zastosowaniu procesu arytmetyzacji wielomian będzie miał postać odpowiednio $W(x)=x$ lub $W(x)=(1-x)$. Jest zatem jasne, że dla wartościowania zmiennej $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ż $n-1$; pokażemy, że jest ona również spełniona dla formuł o długości $n$. Weźmy zatem formułę $\varphi$ o długości $n$ i załóżmy, że $\varphi =\alpha \wedge \beta$. Wielomian $W$ jest zatem postaci $W(x_1,\dots ,x_m)=W_{\alpha }(x_1,\dots ,x_m)*W_{\beta }(x_1,\dots ,x_m)$. Niech $a_1,\dots ,a_m$ będzie wartościowaniem spełniającym dla formuły $\varphi$; jest ono zatem wartościowaniem spełniającym dla $\alpha$ i $\beta$. Formuły $\alpha$ i $\beta$ mają co najwyżej $n-1$ literałów -- korzystając z założenia indukcyjnego, możemy stwierdzić, że:

$W_{\alpha }(a_1,\dots ,a_m)=W_{\beta }(a_1,\dots ,a_m)=1$.

W związku z tym:

$W(a_1,\dots ,a_m)=1$.

Załóżmy teraz, że $a_1,\dots ,a_m$ nie jest wartościowaniem spełniającym dla $\varphi$. Nie jest zatem wartościowaniem spełniającym dla przynajmniej jednej z formuł $\alpha$ lub $\beta$. W związku z tym zachodzi własność:

$W_{\alpha }(a_1,\dots ,a_m)=0$

lub

$W_{\beta }(a_1,\dots ,a_m)=0$.

W konsekwencji:

$W(a_1,\dots ,a_m)=0$.

Dowód przypadku, gdy $\varphi =\alpha \vee \beta$, jest analogiczny.

Ćwiczenie 2.11

Niech $n$ oznacza liczbę -- niekoniecznie różnych -- literałów (zmiennych i ich zaprzeczeń) w formule $\varphi$. Pokaż, że stopień każdej zmiennej w wielomianie $W$ jest nie większy niż $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ż $n-1$ literałach; pokażemy, że jest ona też spełniona dla formuł o $n$ literałach. Weźmy formułę $\varphi$ o $n$ literałach i załóżmy, że jest ona postaci $\varphi =\alpha \wedge \beta$. Oznaczmy długości formuł $\alpha$ i $\beta$ jako $l_{\alpha }$ i $l_{\beta }$. Ustalmy też dowolną zmienną $x_i$ występującą w formule $\varphi$. Z założenia indukcyjnego wiemy, że stopień tej zmiennej w wielomianach $W_{\alpha }$ i $W_{\beta }$ jest co najwyżej równy odpowiednio $l_{\alpha }$ lub $l_{\beta }$. Wielomian otrzymany z formuły $\varphi$ jest postaci $W(x_1,\dots ,x_m)=W_{\alpha }(x_1,\dots ,x_m)*W_{\beta }(x_1,\dots ,x_m)$. Stopień $W$ jako wielomianu zmiennej $x_i$ jest zatem równy co najwyżej $l_{\alpha }+l_{\beta }$ -- liczba ta jest równa ilości literałów w formule $\varphi$.

W przypadku, gdy $\varphi =\alpha \vee \beta$, wielomian $W$ jest postaci:

$W(\dots )=1-(1-W_{\alpha }(\dots ))\cdot (1-W_{\beta }(\dots ))$.

Po dokonaniu mnożenia otrzymamy:

$W(\dots )=W_{\alpha }(\dots )+W_{\beta }(\dots )-W_{\alpha }(\dots )\cdot W_{\beta }(\dots )$.

Jest zatem jasne, że stopień $W$ jako zmiennej $x_i$ jest nie większy niż $l_{\alpha }+l_{\beta }$.

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

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

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

${\mathrm{\forall }}_{a_1,a_2,\dots ,a_i\in \{0,1\}}{f}_i(a_1,a_2,\dots ,a_i)=\sum _{x_{i+1}\in \{0,1\}}\dots \sum _{x_m\in \{0,1\}}{f}_m(a_1,a_2,\dots ,a_i,x_{i+1},\dots ,x_m)$

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

Zauważmy jeszcze, że w wielomianach $f_i$ zachowana jest własność, mówiąca że każda zmienna występuje co najwyżej w stopniu $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 $f_0,\dots ,f_{m-1}$ zleca funkcji $P$. Ta następnie przekazuje funkcji $V$ pewne informacje o wielomianach, na podstawie których $V$ może z dużym prawdopodobieństwem rozstrzygnąć, czy $f_0,\dots ,f_{m-1}$ zostały "uczciwie" obliczone zgodnie z powyższą rekurencyjną procedurą, czy też $P$ próbuje oszukać $V$.

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

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

• Krok 1 (P): Znajdź liczbę pierwszą $p$ z przedziału $[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 $p$, odrzuć słowo wejściowe, jeśli $p$ lub jej certyfikat są nieprawidłowe.
• Krok 3 (P): Oblicz $f_0()$ i prześlij jako wiadomość.
• Krok 4 (V): Sprawdź, czy $f_0()\ge k$ -- jeśli nie to odrzuć słowo wejściowe.
• Krok 5 (P): Oblicz $f_1(z)$ (wielomian ze zmienną $z$) i prześlij jego współczynniki jako wiadomość.
• Krok 6 (V): Sprawdź, czy $f_0()=f_1(0)+f_1(1)$. Wylosuj dowolną liczbę $r_1$ z ${\mathbb{\mathbb{Z}}}_p$ i prześlij ją jako wiadomość,
• Krok 7 (P): Oblicz $f_2(r_1,z)$ (to też jest wielomian z jedną zmienną $z$) i prześlij jego współczynniki jako wiadomość.
• Krok 8 (V): Sprawdź, czy $f_1(r_1)=f_2(r_1,0)+f_2(r_1,1)$. Wylosuj dowolną liczbę $r_2$ z ${\mathbb{\mathbb{Z}}}_p$ i prześlij ją jako wiadomość.
• $\cdots$
• Krok $2m+4$ (V): Sprawdź, czy $f_{m-1}(r_1,\dots ,r_{m-1})=f_m(r_1,\dots ,r_{m-1},0)+f_m(r_1,\dots ,r_{m-1},1)$. Sprawdź, czy $f_m(r_1,\dots ,r_{m-1},z)$ jest wielomianem otrzymanym przez arytmetyzację formuły $\varphi$ i podstawienie $r_1,\dots ,r_{m-1}$ jako pierwszych $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 $\mathrm{\#}SAT(D)$, jest jasne, że funkcja $P$, postępująca zgodnie z powyższym protokołem, zawsze przekona $V$ o tej przynależności. Popatrzmy teraz, co się stanie, gdy słowo wejściowe nie należy do $\mathrm{\#}SAT(D)$; w tym przypadku wartość $f_0()$ podana przez $\overline{P}$ będzie musiała się różnić od wartości prawdziwej (oznaczmy ją jako $\overline{f_0}()$). W związku z tym przynajmniej jedna z wartości $f_1(0)$ lub $f_1(1)$ będzie różna od oczekiwanej -- $\overline{f_1}(0)$ lub $\overline{f_1}(1)$ -- a co za tym idzie wielomian $f_1(z)$ będzie różny od $\overline{f_1}(z)$. Pokażemy teraz fakt będący sednem naszego dowodu: jeżeli wielomian $f_i(r_1,r_2,\dots ,r_{i-1},z)$ jest różny od wielomianu $\overline{f_i}(r_1,r_2,\dots ,r_{i-1},z)$, to z dużym prawdopodobieństwem również $f_{i+1}(r_1,r_2,\dots ,r_i,z)$ będzie różny od $\overline{f_{i+1}}(r_1,r_2,\dots ,r_i,z)$. Zauważmy, że jesli $r_i$ zostanie wylosowane w taki sposób, że $f_i(r_1,\dots ,r_i)=\overline{f_i}(r_1,\dots ,r_i)$, to $\overline{P}$ w kolejnym kroku będzie mógł zwrócić wielomian $\overline{f_{i+1}}(r_1,\dots ,r_i,z)$ -- a zatem skutecznie oszuka $V$. Aby tak się jednak stało wylosowana wartość $r_i$ musi być jednym z punktów, w których $\overline{f_i}(r_1,r_2,\dots ,r_{i-1},z)$ i $\overline{f_i}(r_1,r_2,\dots ,r_{i-1},z)$ są równe. Prawdopodobieństwo takiego zdarzenia to co najwyżej $n/2^n$. Jeżeli $f_i(r_1,\dots ,r_i)\ne \overline{f_i}(r_1,\dots ,r_i)$, to niewątpliwie $f_{i+1}(r_1,\dots ,r_i,0)\ne \overline{f_{i+1}}(r_1,\dots ,r_i,0)$ lub $f_{i+1}(r_1,\dots ,r_i,1)\ne \overline{f_{i+1}}(r_1,\dots ,r_i,1)$ -- a co za tym idzie wielomian $f_{i+1}(r_1,\dots ,r_i,z)$ będzie różny od wielomianu $\overline{f_{i+1}}(r_1,\dots ,r_i,z)$.

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

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

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

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

${Q_1}_{x_1}{Q_2}_{x_2}\dots {Q_m}_{x_m}⟨\varphi ⟩$,

gdzie $Q_i\in \{\mathrm{\exists },\mathrm{\forall }\}$, natomiast $⟨\varphi ⟩$ to formuła $\varphi$ przekształcona w procesie arytmetyzacji. Operacje $Q_i$ definiujemy następująco:

• ${Q_i}_{x_i}W(x_1,x_2,\dots ,x_i,\dots ,x_m)=W(x_1,x_2,\dots ,0,\dots ,x_m)\cdot W(x_1,x_2,\dots ,1,\dots ,x_m)$ gdy $Q_i=\mathrm{\forall }$,
• ${Q_i}_{x_i}W(x_1,x_2,\dots ,x_i,\dots ,x_m)=1-(1-W(x_1,x_2,\dots ,0,\dots ,x_m))\cdot (1-W(x_1,x_2,\dots ,1,\dots ,x_m)),\text{ gdy }{Q}_i=\mathrm{\exists }$.

Możemy w tym momencie spróbować powtórzyć poprzedni dowód, to znaczy zdefiniować ciąg wielomianów $f_0,f_1,\dots ,f_m$ tak, aby $f_m$ był zarytmetyzowaną formułą $\varphi$, a $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:

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

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

• jest liniowy ze względu na $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:

${Q_1}_{x_1}{R}_{x_1}{Q_2}_{x_2}{R}_{x_1}{R}_{x_2}{Q_3}_{x_3}\dots {Q_m}_{x_m}{R}_{x_1}\dots R_{x_m}⟨\varphi ⟩$.

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

Uwaga 2.12

Zauważmy, że w trakcie działania protokołu losujemy $k$ liczb; jest zatem możliwe (i pewne), że w tym procesie $V$ będzie podstawiać w miejsce tej samej zmiennej różne wylosowane liczby. Dla przykładu -- powyżej wylosowaliśmy liczbę ${r^{\prime }}_2$; być może jednak już wcześniej dokonywaliśmy innej operacji na zmiennej $x_2$ i wylosowaliśmy inną liczbę $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 $P$ mógłby osiągnąć większe prawdopodobieństwo skutecznego oszukania $V$.

Jak zauważyliśmy wcześniej, liczba wykonywanych transformacji $k$ jest kwadratowo zależna od $m$; w szczególności natychmiastowe jest oszacowanie $k<(m+1{)}^2$. W związku z tym prawdopodobieństwo, że $V$ zaakceptuje słowo wejściowe nienależące do $QSAT$ jest nie większe niż $(m+1{)}^2/n^3$, co z kolei jest nie większe niż $(n+1{)}^2/n^3=O(1/n)$. Ponownie zatem $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ść $QSAT$ do klasy $IP$. W tym momencie wystarczy zauważyć, że klasa $IP$ jest domknięta ze względu na redukcje wielomianowe; jeśli $L_1$ redukuje się do $L_2$ oraz znamy protokół rozwiązujący $L_2$, to $V$ może w pierwszym kroku dokonać redukcji, po czym postępować zgodnie z protokołem dla $L_2$. Korzystając z faktu, że $QSAT$ jest problemem $PSPACE$-zupełnym, stwierdzamy, że każdy problem z klasy $PSPACE$ zawarty jest w klasie $IP$.

Ćwiczenie 2.13

Wyjaśnij, czemu w protokole $\mathrm{\#}SAT(D)$ potrzebowaliśmy ciała o co najmniej $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 $n^3$. W przypadku $\mathrm{\#}SAT(D)$ ciało ${\mathbb{\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 $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ż $2^n$.