IP (złożoność) - IP (complexity)

W teorii złożoności obliczeniowej klasa IP (co oznacza czas interaktywnego wielomianu) jest klasą problemów rozwiązywanych przez interaktywny system dowodowy . Jest równy klasie PSPACE . Wynik został ustalony w serii artykułów: pierwsza autorstwa Lunda, Karloffa, Fortnowa i Nisan wykazała, że ​​współ-NP miał wiele interaktywnych dowodów dowodzących; a drugi, autorstwa Shamira, wykorzystał ich technikę do ustalenia, że ​​IP=PSPACE. Rezultatem jest słynny przykład, w którym dowód nie relatywizuje .

Koncepcja systemu interaktywnego dowód został po raz pierwszy wprowadzony przez Shafrira Goldwasser , Silvio Micali i Karola Rackoff w 1985. Interaktywny system dowód składa się z dwóch maszyn, a Prover, P , który stanowi dowód, że dany ciąg n jest członkiem jakimś językiem oraz weryfikatora V , który sprawdza, czy przedstawiony dowód jest poprawny. Zakłada się, że weryfikator jest nieskończony w obliczeniach i pamięci, podczas gdy weryfikator jest probabilistyczną maszyną czasu wielomianowego z dostępem do losowego ciągu bitów, którego długość jest wielomianowa o rozmiarze n . Te dwie maszyny wymieniają wielomianową liczbę p ( n ) komunikatów i po zakończeniu interakcji weryfikator musi zdecydować, czy n jest w języku, z tylko 1/3 szansą błędu. (Więc każdy język w BPP jest w IP , ponieważ od tego czasu weryfikator może po prostu zignorować weryfikatora i sam podjąć decyzję.)

Definicja

Język L należy do IP, jeśli istnieje V , P taki, że dla wszystkich Q , w :

${\ Displaystyle w \ w L \ Rightarrow \ Pr [V \ leftrightarrow P {\ tekst { akceptuje}} w] \ geq {\ tfrac {2} {3}}}$

${\ Displaystyle w \ nie \ w L \ Rightarrow \ Pr [V \ leftrightarrow Q {\ tekst { akceptuje}} w] \ leq {\ tfrac {1} {3}}}$

Protokół Artura-Merlina , wprowadzony przez László Babai , ma podobny charakter, z wyjątkiem tego, że liczba rund interakcji jest ograniczona stałą, a nie wielomianem.

Goldwasser i in. wykazali, że protokoły publicznych monet , w których losowe liczby używane przez weryfikatora są dostarczane do sprawdzającego wraz z wyzwaniami, są nie mniej wydajne niż protokoły prywatnej monety. Co najwyżej dwie dodatkowe rundy interakcji są wymagane do odtworzenia efektu protokołu prywatnej monety. Odwrotne włączenie jest proste, ponieważ weryfikator zawsze może przesłać do dowodu wyniki swoich prywatnych rzutów monetą, co dowodzi, że oba typy protokołów są równoważne.

W następnej sekcji dowodzimy, że IP = PSPACE , ważne twierdzenie o złożoności obliczeniowej, które pokazuje, że interaktywny system dowodowy może być użyty do decydowania, czy łańcuch jest członkiem języka w czasie wielomianowym, nawet jeśli tradycyjny dowód PSPACE może być wykładniczo długa.

Dowód IP = PSPACE

Dowód można podzielić na dwie części, pokazujemy, że IP ⊆ PSPACE i PSPACE ⊆ IP .

IP ⊆ PSPACE

W celu wykazania, że IP ⊆ PSPACE , przedstawiamy symulację interaktywnego systemu dowodowego przez wielomianową maszynę kosmiczną. Teraz możemy zdefiniować:

${\ Displaystyle \ Pr [V {\ tekst {akceptuje}} w {\ tekst { zaczynając od}} M_ {j}] = \ max \ nolimits _ {P} \ Pr \ lewo [V \ lewoprawo strzałka P {\ tekst { akceptuje }}w{\text{ począwszy od }}M_{j}\right]}$

i dla każdego 0 ≤ j ≤ p i każdej historii wiadomości M _j indukcyjnie definiujemy funkcję N _{M j} :

${\ Displaystyle N_ {M_ {j}} = {\ Rozpocznij {przypadki} 0 & j = p {\ tekst {i}} m_ {p} = {\ tekst {odrzuć}} \ \ 1 & j = p {\ tekst {i} }m_{p}={\text{accept}}\\\max _{m_{j+1}}N_{M_{j+1}}&j<p{\text{ i }}j{\text{ jest nieparzyste}}\\{\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}&j<p{\text{ i }}j{\text{ jest parzyste }}\\\end{przypadki}}}$

gdzie:

${\ Displaystyle {\ text {Wt-avg}} _ {m_ {j + 1}} N_ {M_ {j + 1}}: = \ suma \ nolimits _ {m_ {j + 1}} \ Pr \ nolimits _ {r}[V(w,r,M_{j})=m_{j+1}]N_{M_{j+1}}}$

gdzie Pr _r jest prawdopodobieństwem przejętym przez losowy ciąg r o długości p . Wyrażenie to jest średnią z N _{M j+1} ważoną prawdopodobieństwem, że weryfikator wysłał wiadomość m _j+1 .

Weź M ₀ jako pustą sekwencję wiadomości, tutaj pokażemy, że N _{M 0} można obliczyć w przestrzeni wielomianowej i że N _{M 0} = Pr[ V akceptuje w ]. Po pierwsze, aby obliczyć N _{M 0} , algorytm może rekurencyjnie obliczyć wartości N _{M j} dla każdego j i M _j . Ponieważ głębokość rekurencji wynosi p , potrzebna jest tylko przestrzeń wielomianowa. Drugim wymaganiem jest to, że potrzebujemy N _{M 0} = Pr[ V akceptuje w ], wartość potrzebną do ustalenia, czy w jest w A. Do udowodnienia tego używamy indukcji w następujący sposób.

Musimy pokazać, że dla każdego 0 ≤ j ≤ p i każdego M _j , N _{M j} = Pr[ V akceptuje w zaczynając od M _j ] i zrobimy to za pomocą indukcji na j . Podstawowym przypadkiem jest udowodnienie dla j = p . Następnie użyjemy indukcji, aby przejść od p do 0.

Podstawowy przypadek j = p jest dość prosty. Ponieważ m _P się zaakceptować czy odrzucić czy m _P jest przyjąć, N _{M p} określa się 1, a Pr [ V przyjmuje w zaczynając M _j ] = 1, ponieważ strumień komunikatów oznacza zatwierdzania i żądanie to prawda. Jeśli m _p jest odrzucone, argument jest bardzo podobny.

Dla hipotezy indukcyjnej zakładamy, że dla pewnego j +1 ≤ p i dowolnej sekwencji komunikatów M _j+1 , N _{M j+1} = Pr[ V akceptuje w zaczynając od M _j+1 ], a następnie udowodnij hipotezę dla j i dowolna sekwencja komunikatów M _j .

Jeśli j jest parzyste, m _j+1 jest wiadomością od V do P . Zgodnie z definicją N _{M j} ,

${\ Displaystyle N_ {M_ {j}} = \ suma \ nolimits _ {m_ {j + 1}} \ pr \ nolimits _ {r} \ lewo [V (w, r, M_ {j}) = m_ {j +1}\right]N_{M_{j+1}}.}$

Następnie, zgodnie z hipotezą indukcyjną, możemy powiedzieć, że to jest równe

${\ Displaystyle \ suma \ nolimits _ {m_ {j + 1}} \ pr \ nolimits _ {r} \ lewo [V (w, r, M_ {j}) = m_ {j + 1} \ po prawej] * \ Pr \left[V{\text{ akceptuje }}w{\text{ zaczynając od }}M_{j+1}\right].}$

Wreszcie, z definicji, widzimy, że jest to równe Pr[ V akceptuje w zaczynając od M _j ].

Jeśli j jest nieparzyste, m _j+1 jest wiadomością od P do V . Zgodnie z definicją,

${\ Displaystyle N_ {M_ {j}} = \ max \ nolimits _ {m_ {j + 1}} N_ {M_ {j + 1}}.}$

Następnie, zgodnie z hipotezą indukcyjną, równa się to

${\ Displaystyle \ max \ nolimits _ {m_ {j + 1}} * \ Pr [V {\ tekst {akceptuje}} w {\ tekst { od }} M_ {j + 1}].}$

Jest to równe Pr[ V akceptuje w zaczynając od M _j ], ponieważ:

${\ Displaystyle \ max \ nolimits _ {m_ {j + 1}} \ Pr [V {\ tekst {akceptuje}} w {\ tekst { od }} M_ {j + 1}] \ leq \ Pr [V { \text{ akceptuje w zaczynając od }}M_{j}]}$

ponieważ dowodzący po prawej stronie mógłby wysłać komunikat m _j+1, aby zmaksymalizować wyrażenie po lewej stronie. I:

${\ Displaystyle \ max \ nolimits _ {m_ {j + 1}} \ Pr \ lewo [V {\ tekst {akceptuje}} w {\ tekst { od }} M_ {j + 1} \ po prawej] \ geq \ Pr \left[V{\text{ akceptuje }}w{\text{ zaczynając od }}M_{j}\right]}$

Ponieważ ten sam Prover nie może zrobić nic lepszego niż wysłanie tej samej wiadomości. Tak więc obowiązuje to, czy i jest parzyste, czy nieparzyste, a dowód, że IP ⊆ PSPACE jest kompletny.

Tutaj skonstruowaliśmy wielomianową maszynę przestrzenną, która używa najlepszego dowodzącego P dla konkretnego łańcucha w w języku A . Używamy tego najlepszego dowodzenia zamiast dowodzenia z losowymi bitami wejściowymi, ponieważ jesteśmy w stanie wypróbować każdy zestaw losowych bitów wejściowych w przestrzeni wielomianowej. Ponieważ symulowaliśmy interaktywny system dowodowy z wielomianową maszyną przestrzenną, pokazaliśmy, że IP ⊆ PSPACE , zgodnie z potrzebami.

PSPACE ⊆ IP

Aby zilustrować technikę, która zostanie użyta do udowodnienia PSPACE ⊆ IP , najpierw udowodnimy słabsze twierdzenie, które udowodnili Lund i in.: #SAT ∈ IP . Następnie używając pojęć z tego dowodu rozszerzymy go, aby pokazać, że TQBF ∈ IP . Ponieważ TQBF ∈ PSPACE -complete i TQBF ∈ IP to PSPACE ⊆ IP .

#SAT jest członkiem IP

Zaczynamy od pokazania, że ​​#SAT jest w IP , gdzie:

${\displaystyle \#{\text{SAT}}=\left\{\langle \varphi ,k\rangle \ :\ \varphi {\text{to wzór CNF z dokładnie }}k{\text{spełniającym zadania }}\Prawidłowy\}.}$

Zauważ, że różni się to od normalnej definicji #SAT , ponieważ jest to problem decyzyjny, a nie funkcja.

Najpierw używamy arytmetyzacji, aby odwzorować wzór logiczny z n zmiennymi, φ( b ₁ , ..., b _n ) na wielomian p _φ ( x ₁ , ..., x _n ), gdzie p _φ naśladuje φ w tym p _φ wynosi 1, jeśli φ jest prawdziwe, a 0 w przeciwnym razie, pod warunkiem, że zmiennym p _φ są przypisane wartości logiczne. Operacje logiczne ∨, ∧ i ¬ stosowane w φ są symulowane w p _φ przez zastąpienie operatorów w φ, jak pokazano w poniższej tabeli.

Reguły arytmetyczne przekształcania formuły Boole'a φ( b ₁ , ..., b _n ) na wielomian p _φ ( x ₁ , ..., x _n )

∧ b	ab
∨ b	a ∗ b  := 1 − (1 − a )(1 − b )
¬ a	1 − a

Na przykład φ = a ∧ ( b ∨ ¬ c ) zostanie przekształcone w wielomian w następujący sposób:

${\ Displaystyle {\ zacząć {wyrównany} p_ {\ varphi} & = a \ klin (b \ vee \ neg c) \ \ & = a \ klin \ lewo (b * (1-c) \ prawo) \ \ & =a\wedge \left(1-(1-b)(1-(1-c))\right)\\&=a\left(1-(1-b)(1-(1-c)) \right)\\&=a-(ac-abc)\end{aligned}}}$

Operacji AB i * b każdego związku w wielomian o stopniu ograniczonym przez sumę stopni wielomianów dla i B , a tym samym stopień każdej zmiennej jest co najwyżej długość cp.

Teraz niech F będzie ciałem skończonym o rzędzie q > 2 ⁿ ; także żądać q wynosi co najmniej 1000. Dla każdej 0 ≤ i ≤ n , określenie funkcji f _I o F , o parametrach , a pojedyncza zmienna _i w F : 0 ≤ i ≤ n i wylotem ${\ Displaystyle a_ {1}, \ kropki, a_ {i-1} \ w F}$${\ Displaystyle a_ {1}, \ kropki, a_ {i} \ w F}$

${\ Displaystyle f_ {i} (a_ {1}, \ kropki, a_ {i}) = \ suma \ nolimity _ {a_ {i + 1}, \ kropki, a_ {n} \ w \ {0,1\ }}p(a_{1},\kropki ,a_{n}).}$

Zauważ, że wartość f ₀ jest liczbą spełniających przypisań φ. f ₀ jest funkcją void, bez zmiennych.

Teraz protokół dla #SAT działa w następujący sposób:

• Faza 0 : Dowód P wybiera liczbę pierwszą q > 2 ⁿ i oblicza f ₀ , następnie wysyła q i f ₀ do weryfikatora V . V sprawdza, czy q jest liczbą pierwszą większą niż max(1000, 2 ⁿ ) i czy f ₀ () = k .
• Faza 1 : P wysyła współczynniki f ₁ ( z ) jako wielomian w z. V weryfikuje, czy stopień f ₁ jest mniejszy niż n i czy f ₀ = f ₁ (0) + f ₁ (1). (Jeśli nie, V odrzuca). V teraz wysyła losową liczbę r ₁ z F do P .
• Faza i : P wysyła współczynniki jako wielomian w z . V sprawdza się, czy stopień F _i mniej niż n i . (Jeśli nie V odrzuca). V teraz wysyła losową liczbę r _i od F do P .${\ Displaystyle f_ {i} (r_ {1}, \ kropki, r_ {i-1}, z)}$${\ Displaystyle f_ {i-1} (r_ {1}, \ kropki, r_ {i-1}) = f_ {i} (r_ {1}, \ kropki, r_ {i-1}, 0) + f_ {i}(r_{1},\kropki ,r_{i-1},1)}$
• Faza n+1 : V ocenia, aby porównać z wartością . Jeśli są równe, V akceptuje, w przeciwnym razie V odrzuca.${\ Displaystyle p (r_ {1}, \ kropki, r_ {n})}$${\ Displaystyle f_ {n} (r_ {1}, \ kropki, r_ {n})}$

Zauważ, że jest to algorytm monety publicznej.

Jeśli φ ma k zadowalających przypisań, to oczywiście V zaakceptuje. Jeśli φ nie ma k spełniających przypisań, zakładamy, że istnieje dowodzący, który próbuje przekonać V, że φ ma k spełniających przypisań. Pokazujemy, że można to zrobić tylko z małym prawdopodobieństwem. ${\ Displaystyle {\ tylda {P}}}$

Aby zapobiec odrzuceniu V w fazie 0, musi wysłać nieprawidłową wartość do P . Następnie, w fazie 1, musi wysłać niepoprawny wielomian z właściwością, która . Kiedy V wybiera losowe r ₁ do wysłania do P , ${\ Displaystyle {\ tylda {P}}}$${\displaystyle {\tylda {f}}_{0}()}$${\ Displaystyle {\ tylda {P}}}$${\displaystyle {\tylda {f}}_{1}}$${\ Displaystyle {\ tylda {f}} _ {1} (0) + {\ tylda {f}} _ {1} (1) = {\ tylda {f}} _ {0}()}$

${\ Displaystyle \ Pr \ lewo [{\ tylda {f}} _ {1} (r_ {1}) = f_ {1} (r_ {1}) \ prawo] < {\ tfrac {1} {n ^ { 2}}}.}$

Dzieje się tak, ponieważ wielomian w pojedynczej zmiennej stopnia co najwyżej d może mieć nie więcej niż d pierwiastków (chyba że zawsze daje 0). Zatem dowolne dwa wielomiany w jednej zmiennej stopnia co najwyżej d mogą być równe tylko wd miejscach. Ponieważ | F | > 2 ⁿ szanse na to, że r ₁ jest jedną z tych wartości wynoszą co najwyżej, jeśli n > 10, lub co najwyżej ( n /1000) ≤ ( n / n ³ ), jeśli n ≤ 10. ${\displaystyle n/2^{n}<n/n^{3}}$

Uogólniając tę ​​ideę dla innych faz mamy dla każdego 1 ≤ i ≤ n if

${\ Displaystyle {\ tylda {f}} _ {i-1} (r_ {1}, \ kropki, r_ {i-1}) \ neq f_ {i-1} (r_ {1}, \ kropki, r_ {i-1}),}$

Następnie do R _i wybrana losowo z F ,

${\ Displaystyle \ Pr \ lewo [{\ tylda {f}} (r_ {1}, \ kropki, r_ {i}) = f_ {i} (r_ {1}, \ kropki, r_ {i}) \ prawo ]\leq {\tfrac {1}{n^{2}}}.}$

Istnieje n faz, więc prawdopodobieństwo, że V wybiera na pewnym etapie dogodne r _i jest co najwyżej 1/ n . Zatem żaden dowodzący nie może sprawić, że weryfikator zaakceptuje z prawdopodobieństwem większym niż 1/ n . Z definicji widać również, że weryfikator V działa w probabilistycznym czasie wielomianowym. Zatem #SAT ∈ IP . ${\ Displaystyle {\ tylda {P}}}$

TQBF jest członkiem IP

Aby pokazać, że PSPACE jest podzbiorem IP , musimy wybrać problem z pełnym PSPACE i pokazać, że jest to IP . Gdy to pokażemy, to jasne, że PSPACE ⊆ IP . Zademonstrowana tutaj technika dowodowa jest przypisywana Adi Shamirowi .

Wiemy, że TQBF jest w PSPACE-Complete . Niech ψ będzie więc kwantyfikowanym wyrażeniem boolowskim:

${\ Displaystyle \ psi = {\ mathsf {Q}} _ {1} x_ {1} \ kropki {\ mathsf {Q}} _ {m} x_ {m} [\ varphi]}$

gdzie φ jest formułą CNF. Wtedy Q _i jest kwantyfikatorem, albo ∃ albo ∀. Teraz f _i jest takie samo jak w poprzednim dowodzie, ale teraz zawiera również kwantyfikatory.

${\ Displaystyle f_ {i} (a_ {1}, \ kropki, a_ {i}) = {\ zacząć {przypadki} f_ {i} (a_ {1}, \ kropki, a_ {m}) = 1 i {\ mathsf {Q}}_{i+1}x_{i+1}\dots {\mathsf {Q}}_{m}x_{m}[\varphi (a_{1},\dots ,a_{i} )]{\text{ jest prawdziwe}}\\0&{\text{otherwise}}\end{cases}}}$

Tutaj φ( a ₁ , ..., a _i ) to φ z a ₁ do a _i podstawionym za x ₁ do x _i . Zatem f ₀ jest wartością logiczną ψ. Aby wykonać arytmetykę ψ, musimy zastosować następujące reguły:

${\ Displaystyle f_ {i} (a_ {1}, \ kropki, a_ {i}) = {\ zacząć {przypadki} f_ {i + 1} (a_ {1}, \ kropki, a_ {i}, 0) \cdot f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+1}=\forall \\f_{i+1}( a_{1},\dots ,a_{i},0)*f_{i+1}(a_{1},\dots ,a_{i},1)&{\mathsf {Q}}_{i+ 1}=\istnieje \end{przypadki}}}$

gdzie jak poprzednio definiujemy x ∗ y = 1 − (1 −  x )(1 −  y ).

Używając metody opisanej w #SAT, musimy zmierzyć się z problemem, że dla dowolnego f _i stopień wynikowego wielomianu może podwoić się z każdym kwantyfikatorem. Aby temu zapobiec, musimy wprowadzić nowy operator redukcji R, który zmniejszy stopnie wielomianu bez zmiany ich zachowania na wejściach logicznych.

Więc teraz, zanim zaczniemy arytmetyzować , wprowadzamy nowe wyrażenie: ${\ Displaystyle \ psi = {\ mathsf {Q}} _ {1} x_ {1} \ kropki {\ mathsf {Q}} _ {m} x_ {m} [\ varphi]}$

${\ Displaystyle \ psi '= {\ mathsf {Q}} _ {1} \ mathsf {R} x_ {1} {\ mathsf {Q}} _ {2} \ mathsf {R} x_ {1} \ mathsf { R} x_{2}\dots {\mathsf {Q}}_{m}\mathrm {R} x_{1}\dots \mathrm {R} x_{m}[\varphi ]}$

lub inaczej:

${\ Displaystyle \ psi '={\mathsf {S}}_{1}y_{1}\dots {\mathsf {S}}_{k}y_{k}[\varphi],\qquad {\text{ gdzie }}{\mathsf {S}}_{i}\in \{\forall ,\exists ,\mathrm {R} \},\ y_{i}\in \{x_{1},\dots ,x_ {m}\}}$

Teraz dla każdego i ≤ k definiujemy funkcję f _I . Definiujemy również jako wielomian p ( x ₁ , ..., x _m ), który otrzymujemy przez arytmetykę φ. Teraz, aby utrzymać stopień wielomianu nisko, możemy zdefiniować f _I pod względem f _{i + 1} : ${\ Displaystyle f_ {k} (x_ {1}, \ kropki, x_ {m})}$

${\ Displaystyle {\ tekst {jeśli}} {\ mathsf {S}} _ {i + 1} = \ dla wszystkich, \ quad f_ {i} (a_ {1}, \ kropki, a_ {i}) = f_ { i+1}(a_{1},\dots ,a_{i},0)\cdot f_{i+1}(a_{1},\dots ,a_{i},1)}$

${\ Displaystyle {\ tekst {jeśli}} {\ mathsf {S}} _ {i + 1} = \ istnieje, \ quad f_ {i} (a_ {1}, \ kropki, a_ {i}) = f_ { i+1}(a_{1},\kropki ,a_{i},0)*f_{i+1}(a_{1},\kropki ,a_{i},1)}$

${\ Displaystyle {\ tekst {Jeśli}} {\ mathsf {S}} _ {i + 1} = \ operatorname {R}, \ quad f_ {i} (a_ {1}, \ kropki, a_ {i}, a)=(1-a)f_{i+1}(a_{1},\dots ,a_{i},0)+af_{i+1}(a_{1},\dots ,a_{i} ,1)}$

Teraz widzimy, że operacja redukcji R nie zmienia stopnia wielomianu. Ważne jest również, aby zobaczyć, że operacja R _x nie zmienia wartości funkcji na wejściach binarnych. Zatem f ₀ jest nadal wartością logiczną ψ, ale wartość R _x daje wynik, który jest liniowy względem x . Również po dowolnym dodajemy ψ′ w celu zmniejszenia stopnia do 1 po arytmetyce . ${\ Displaystyle {\ mathsf {Q}} _ {i} x_ {i}}$${\ Displaystyle \ operatorname {R} _ {x_ {1}} \ kropki \ operatorname {R} _ {x_ {i}}}$${\ Displaystyle {\ mathsf {Q}} _ {i}}$

Opiszmy teraz protokół. Jeśli n jest długością ψ, wszystkie operacje arytmetyczne w protokole dotyczą pola o rozmiarze co najmniej n ^4, gdzie n jest długością ψ.

• Faza 0 : P → V : P wysyła f ₀ do V . V sprawdza, czy f ₀ = 1 i odrzuca, jeśli nie.
• Faza 1 : P → V : P wysyła f ₁ ( z ) do V . V używa współczynników do obliczenia f ₁ (0) i f ₁ (1). Następnie sprawdza, czy stopień wielomianu wynosi co najwyżej n i czy następujące tożsamości są prawdziwe:

${\ Displaystyle f_ {0} (\ varnothing ) = {\ zacząć {przypadki} f_ {1} (0) \ cdot f_ {1} (1) i {\ tekst {jeśli}} {\ mathsf {S}} = \forall \\f_{1}(0)*f_{1}(1)&{\text{ if }}{\mathsf {S}}=\istnieje .\\(1-r)f_{1}( 0)+rf_{1}(1)&{\text{ if }}{\mathsf {S}}=\mathrm {R} .\end{cases}}}$

Jeśli któryś z nich się nie powiedzie, odrzuć.

• Faza i : P → V : P wysyła jako wielomian w z . r ₁ oznacza poprzednio ustawione wartości losowe dla${\ Displaystyle f_ {i} (r_ {1}, \ kropki, r_ {i-1}, z)}$${\displaystyle r_{1},\kropki,r_{i-1}}$

V używa współczynników do oceny i . Następnie sprawdza, czy stopień wielomianu wynosi co najwyżej n i czy następujące tożsamości są prawdziwe: ${\ Displaystyle f_ {i} (r_ {1}, \ kropki, r_ {i-1}, 0)}$${\ Displaystyle f_ {i} (r_ {1}, \ kropki, r_ {i-1}, 1)}$

${\ Displaystyle f_ {i-1} (r_ {1}, \ kropki, r_ {i-1}) = {\ rozpocząć {przypadki} f_ {i} (r_ {1}, \ kropki, r_ {i-1 },0)\cdot f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\forall \\f_{i}(r_{1} ,\dots ,r_{i-1},0)*f_{i}(r_{1},\dots ,r_{i-1},1)&{\mathsf {S}}=\istnieje .\end {sprawy}}}$

${\ Displaystyle f_ {i-1} (r_ {1} \ kropki r) = (1-r) f_ {i} (r_ {1}, \ kropki, r_ {i-1}, 0) + RF_ {i }(r_{1},\dots ,r_{i-1},1){\text{ if }}{\mathsf {S}}=\mathrm {R} .}$

Jeśli któryś z nich się nie powiedzie, odrzuć.

V → P : V wybiera losowe r z F i wysyła je do P. (Jeśli to r zastępuje poprzednie r ). ${\displaystyle {\mathsf {S}}=\mathrm {R}}$

Przejdź do fazy i  +1, gdzie P musi przekonać V, że ma rację. ${\displaystyle f_{i}(r_{1},\kropki,r)}$

• Faza k +1 : V ocenia . Następnie sprawdza, czy jeśli są równe, to V akceptuje, w przeciwnym razie V odrzuca.${\displaystyle p(r_{1},\kropki,r_{m})}$${\ Displaystyle p (r_ {1}, \ kropki, r_ {m}) = f_ {k} (r_ {1}, \ kropki, r_ {m})}$

To jest koniec opisu protokołu.

Jeśli ψ jest prawdziwe, V zaakceptuje, gdy P postępuje zgodnie z protokołem. Podobnie, jeśli jest złośliwym testerem, który kłamie, i jeśli ψ jest fałszywe, to będzie musiał leżeć w fazie 0 i wysłać jakąś wartość dla f ₀ . Jeśli na fazy I , V ma niepoprawną wartość dla później i prawdopodobnie będzie również błędne, i tak dalej. Prawdopodobieństwo szczęścia na jakimś losowym r jest co najwyżej stopniem wielomianu podzielonego przez rozmiar pola: . Protokół przechodzi przez fazy O ( n ² ), więc prawdopodobieństwo, że w pewnej fazie będzie szczęśliwy, wynosi ≤ 1/ n . Jeśli nigdy nie ma szczęścia, V odrzuci w fazie k +1. ${\ Displaystyle {\ tylda {P}}}$${\ Displaystyle {\ tylda {P}}}$${\ Displaystyle f_ {i-1} (r_ {1}, \ kropki)}$${\displaystyle f_{i}(r_{1},\kropki ,0)}$${\displaystyle f_{i}(r_{1},\kropki,1)}$${\ Displaystyle {\ tylda {P}}}$${\ Displaystyle n/n ^ {4}}$${\ Displaystyle {\ tylda {P}}}$${\ Displaystyle {\ tylda {P}}}$

Ponieważ wykazaliśmy teraz, że zarówno IP ⊆ PSPACE jak i PSPACE ⊆ IP , możemy wnioskować, że IP = PSPACE zgodnie z potrzebami. Co więcej, pokazaliśmy, że każdy algorytm IP może być traktowany jako public-coin, ponieważ redukcja z PSPACE do IP ma tę właściwość.

Warianty

Istnieje szereg wariantów IP, które nieznacznie modyfikują definicję interaktywnego systemu dowodowego. Podsumowujemy tutaj niektóre z bardziej znanych.

zanurzać

Podzbiór IP to deterministyczna klasa Interactive Proof , która jest podobna do IP, ale ma deterministyczny weryfikator (tj. bez losowości). Ta klasa jest równa NP .

Doskonała kompletność

Równoważna definicja OD zastępuje warunek, że interakcja powiedzie się z dużym prawdopodobieństwem na smyczki w języku z wymogiem, że zawsze udaje:

${\ Displaystyle w \ w L \ Rightarrow \ Pr [V \ leftrightarrow P {\ tekst {akceptuje}} w] = 1}$

To pozornie silniejsze kryterium „doskonałej kompletności” nie zmienia klasy złożoności IP , ponieważ każdy język z interaktywnym systemem dowodowym może otrzymać interaktywny system dowodowy o doskonałej kompletności.

MIP

W 1988 Goldwasser i in. stworzył jeszcze potężniejszy interaktywny system dowodowy oparty na IP o nazwie MIP, w którym są dwa niezależne dowodzące. Dwaj weryfikatorzy nie mogą się komunikować, gdy weryfikator zaczął wysyłać do nich wiadomości. Tak jak łatwiej jest stwierdzić, czy przestępca kłamie, jeśli on i jego partner są przesłuchiwani w osobnych pokojach, tak znacznie łatwiej jest wykryć złośliwego dowodzącego próbującego oszukać weryfikatora, jeśli jest inny dowodzący, z którym może to sprawdzić. W rzeczywistości jest to tak pomocne, że Babai, Fortnow i Lund byli w stanie wykazać, że MIP = NEXPTIME , klasa wszystkich problemów możliwych do rozwiązania przez niedeterministyczną maszynę w czasie wykładniczym , bardzo duża klasa. Ponadto wszystkie języki w NP mają dowody z wiedzą zerową w systemie MIP , bez żadnych dodatkowych założeń; jest to znane tylko w przypadku IP przy założeniu istnienia funkcji jednokierunkowych.

IPP

IPP ( unbounded IP ) to wariant IP, w którym weryfikator BPP zastępujemy weryfikatorem PP . Dokładniej, modyfikujemy warunki kompletności i rzetelności w następujący sposób:

• Kompletność : jeśli w języku występuje ciąg znaków, uczciwy weryfikator zostanie przekonany o tym fakcie przez uczciwego dowodzącego z prawdopodobieństwem co najmniej 1/2.
• Solidność : jeśli ciąg znaków nie jest w języku, żaden dowodzący nie może przekonać uczciwego weryfikatora, że ​​jest w języku, chyba że z prawdopodobieństwem mniejszym niż 1/2.

Chociaż IPP równa się również PSPACE , protokoły IPP zachowują się zupełnie inaczej niż IP w odniesieniu do wyroczni : IPP = PSPACE w odniesieniu do wszystkich wyroczni, podczas gdy IP ≠ PSPACE w odniesieniu do prawie wszystkich wyroczni.

QIP

QIP to wersja IP zastępującaweryfikator BPP przez weryfikator BQP , gdzie BQP to klasa problemów rozwiązywanych przez komputery kwantowe w czasie wielomianowym. Wiadomości składają się z kubitów. W 2009 roku Jain, Ji, Upadhyay i Watrous udowodnili, że QIP równa się również PSPACE , co oznacza, że ​​zmiana ta nie daje dodatkowej mocy protokołowi. Obejmuje to poprzedni wynik Kitaeva i Watrousa, że QIP jest zawarty w EXPTIME, ponieważ QIP = QIP [3], więc więcej niż trzy rundy nigdy nie są potrzebne.

compIP

Podczas gdy IPP i QIP dają większą moc weryfikatorowi, system compIP ( konkurencyjny system IP proof ) osłabia warunek kompletności w sposób, który osłabia weryfikatora:

• Kompletność : jeśli napis jest w języku L , uczciwy weryfikator zostanie o tym przekonany przez uczciwego dowodzącego z prawdopodobieństwem co najmniej 2/3. Co więcej, dowodzący zrobi to w probabilistycznym czasie wielomianowym, mając dostęp do wyroczni dla języka L .

Zasadniczo czyni to z testera maszynę BPP z dostępem do wyroczni dla języka, ale tylko w przypadku kompletności, a nie solidności. Koncepcja polega na tym, że jeśli język znajduje się w compIP , interaktywne udowodnienie go jest w pewnym sensie tak proste, jak podjęcie decyzji. Z wyrocznią udowadniający może łatwo rozwiązać problem, ale jego ograniczona moc znacznie utrudnia przekonanie weryfikatora do czegokolwiek. W rzeczywistości, compIP nie jest nawet znane ani nie uważa się, że zawiera NP .

Z drugiej strony taki system może rozwiązać niektóre problemy uważane za trudne. Nieco paradoksalnie, chociaż uważa się, że taki system nie jest w stanie rozwiązać wszystkich NP , może z łatwością rozwiązać wszystkie problemy NP-zupełne ze względu na samoredukowalność. Wynika to z faktu, że jeśli język L nie jest NP- trudny, to dowodzący ma znacznie ograniczoną moc (nie może już rozstrzygać wszystkich NP problemów swoją wyrocznią).

Dodatkowo problem braku izomorfizmu grafów (który jest klasycznym problemem w IP ) występuje również w compIP , ponieważ jedyną trudną operacją, jaką musi wykonać program dowodzący , jest testowanie izomorfizmu, które może rozwiązać za pomocą wyroczni. Nierezydualność kwadratowa i izomorfizm grafu występują również w compIP . Uwaga, kwadratowa nieresztkowa (QNR) jest prawdopodobnie łatwiejszym problemem niż izomorfizm grafu, ponieważ QNR jest w UP przecina się co-UP .

Uwagi

Bibliografia

• Babai, L. Teoria grup handlowych dla losowości. W materiałach XVII Sympozjum ACM z Teorii Obliczeń. ACM, Nowy Jork, 1985, s. 421-429.
• Shafi Goldwasser , Silvio Micali i Charles Rackoff . Złożoność wiedzy o interaktywnych systemach dowodowych . Materiały z XVII Sympozjum Teorii Obliczeń ACM , Providence, Rhode Island. 1985, s. 291-304. Rozszerzony streszczenie
• Shafi Goldwasser i Michael Sipser. Monety prywatne a monety publiczne w interaktywnych systemach dowodowych . Materiały z XVIII Dorocznego Sympozjum ACM z Teorii Obliczeń . ACM, Nowy Jork, 1986, s. 59-68.
• Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [1]
• Lund, C. , Fortnow, L. , Karloff, H., Nisan, N. Metody algebraiczne dla interaktywnych systemów dowodowych. W materiałach 31 Sympozjum Podstaw Informatyki. IEEE, Nowy Jork, 1990, s. 2-90.
• Adi Szamir. IP = PSPACE . Dziennik ACM , t. 39, z. 4, s. 869-877. Październik 1992.
• Aleksandra Shena. IP=PSpace: Uproszczony dowód . J.ACM, t. 39(4), s. 878–880, 1992.
• Złożoność Zoo : IP , MIP , IPP , QIP , QIP(2) , compIP , frIP