IP (Komplexität)

Im Computerkomplexitätstheorie, die Klasse IP (Was für interaktive Polynomzeit steht) ist die Klasse von Problemen, die durch ein lösbar sind Interaktives Proof -System. Es ist gleich der Klasse PSPACE. Das Ergebnis wurde in einer Reihe von Papieren festgelegt: die erste von Lund, Karloff, Fortnow und Nisan zeigten, dass CO-NP mehrere interaktive Beweise für interaktive Prover hatte;^[1] und der zweite von Shamir verwendete ihre Technik, um diesen IP = PSPACE festzustellen.^[2] Das Ergebnis ist ein berühmtes Beispiel, bei dem der Beweis nicht relativieren.^[3]

Das Konzept eines interaktiven Proof -Systems wurde zuerst von eingeführt von SHAFI GOLDSER, Silvio Micali, und Charles Rackoff 1985. Ein interaktives Proof -System besteht aus zwei Maschinen, einem Prover, P, was einen Beweis darstellt, dass eine gegebene Saite n ist ein Mitglied einiger Spracheund ein Verifizierer, V, das überprüft, ob der vorgestellte Beweis korrekt ist. Es wird angenommen n. Diese beiden Maschinen tauschen eine Polynomzahl aus, p(n) von Nachrichten und sobald die Interaktion abgeschlossen ist, muss der Überprüfer entscheiden, ob oder nicht n ist in der Sprache, mit nur 1/3 Fehlerwahrscheinlichkeit. (Also jede Sprache in BPP ist in IPSeitdem konnte der Verifizierer den Prover einfach ignorieren und die Entscheidung selbst treffen.)

Definition

Eine Sprache L gehört IP Wenn es existiert V, P so dass für alle Q, w:

$oder$

$oder$

Das Arthur -Merlin -Protokoll, Vorgestellt von László Babai, ist ähnlicher Natur, außer dass die Anzahl der Wechselwirtungen eher durch eine Konstante als durch ein Polynom begrenzt ist.

Goldwasser et al. haben das gezeigt öffentliche Coin Protokolle, bei denen dem Prover zusammen mit den Herausforderungen die vom Verifizierer verwendeten Zufallszahlen zur Verfügung gestellt werden, sind nicht weniger leistungsstark als private Coin-Protokolle. In den meisten zwei weiteren Wechselwirkungsprüfungen sind erforderlich, um die Wirkung eines privaten Coin-Protokolls zu replizieren. Die entgegengesetzte Einbeziehung ist unkompliziert, da der Überprüfer immer an den Prover die Ergebnisse ihrer privaten Münzschläge senden kann, was beweist, dass die beiden Arten von Protokollen gleichwertig sind.

Im folgenden Abschnitt beweisen wir das IP = PSPACE, ein wichtiger Satz in der rechnerischen Komplexität, das zeigt, dass ein interaktives Proof -System verwendet werden kann, um zu entscheiden, ob eine Zeichenfolge ein Mitglied einer Sprache in Polynomzeit ist, obwohl die traditionellen PSPACE Der Beweis kann exponentiell lang sein.

Beweis von IP = PSPACE

Der Beweis kann in zwei Teilen geteilt werden, wir zeigen das IP ⊆ PSPACE und PSPACE ⊆ IP.

IP ⊆ PSPACE

Um das zu demonstrieren IP ⊆ PSPACEWir präsentieren eine Simulation eines interaktiven Beweissystems durch eine Polynomraummaschine. Jetzt können wir definieren:

${\displaystyle \Pr[V{\text{ accepts }}w{\text{ starting at }}M_{j}]=\max \nolimits _{P}\Pr \left[V\leftrightarrow P{\text{ Akzeptiert}} W {\ text {Start bei}} m_ {j} \ right]}$

und für jede 0 ≤ j ≤ p und jeder Nachrichtengeschichte M_jWir definieren die Funktion induktiv N_Mj:

$oder } m_ {p} = {\ text {Akzeptieren}} \\\ max _ {m_ {j+1}} n_ {m_ {j+1}} & j <p {\ text {und} j {\ text {{{{\ text ist ungerade}} \\ {\ text {wt-avg}} _ {m_ {j+1}} n_ {m_ {j+1}} & j <p {\ text {und}} j {\ text {IS sogar }} \\\ end {cases}}}$

wo:

${\displaystyle {\text{wt-avg}}_{m_{j+1}}N_{M_{j+1}}:=\sum \nolimits _{m_{j+1}}\Pr \nolimits _ {r} [v (w, r, m_ {j}) = m_ {j+1}] n_ {m_ {j+1}}}$

wo pr_r ist die Wahrscheinlichkeit, die zufällige Zeichenfolge übernommen wird r von Länge p. Dieser Ausdruck ist der Durchschnitt von N_MJ+1, gewicht m_J+1.

Nehmen M₀ Um die leere Nachrichtensequenz zu sein, werden wir hier zeigen N_M0 kann im Polynomraum berechnet werden, und das N_M0 = PR [V Akzeptiert w]. Erstens, um zu berechnen N_M0Ein Algorithmus kann die Werte rekursiv berechnen N_Mj für jeden j und M_j. Da ist die Tiefe der Rekursion pEs ist nur Polynomraum erforderlich. Die zweite Anforderung ist, dass wir brauchen N_M0 = PR [V Akzeptiert w] der Wert, der erforderlich ist, um festzustellen, ob w ist in A. Wir verwenden die Induktion, um dies wie folgt zu beweisen.

Wir müssen das für jeden 0 ≤ zeigen j ≤ p Und jeder M_j, N_Mj = PR [V Akzeptiert w beginnt um M_j], und wir werden dies mit der Induktion tun j. Der Basisfall ist zu beweisen, dass j = p. Dann werden wir die Induktion verwenden, um von zu gehen p bis 0.

Der Basisfall von j = p ist ziemlich einfach. Seit m_p wird entweder akzeptiert oder ablehnt, wenn m_p ist akzeptiert, N_Mp ist definiert als 1 und PR [[V Akzeptiert w beginnt um M_j] = 1 Da der Nachrichtenstrom die Akzeptanz angibt, ist der Anspruch daher wahr. Wenn m_p ist abgelehnt, das Argument ist sehr ähnlich.

Für die induktive Hypothese nehmen wir das für einige an j+1 ≤ p und jede Nachrichtensequenz M_J+1, N_MJ+1 = PR [V Akzeptiert w beginnt um M_J+1] und beweisen dann die Hypothese für j und jede Nachrichtensequenz M_j.

Wenn j ist gerade, m_J+1 ist eine Nachricht von V zu P. Durch die Definition von N_MjAnwesend

$oder +1} \ rechts] n_ {m_ {j+1}}.}$

Dann können wir durch die induktive Hypothese sagen, dass dies gleich ist

$oder Pr \ links [v {\ text {akzeptiert}} w {\ text {startet bei}} m_ {j+1} \ rechts].}$

Schließlich können wir per Definition sehen, dass dies gleich PR [ist [[V Akzeptiert w beginnt um M_j].

Wenn j ist ungerade, m_J+1 ist eine Nachricht von P zu V. Per Definition,

${\ displayStyle n_ {m_ {j}} = \ max \ nolimits _ {m_ {j+1}} n_ {m_ {j+1}}.}$

Dann ist dies durch die induktive Hypothese gleich

$oder$

Dies ist gleich PR [[V Akzeptiert w beginnt um M_j] seit:

$oder \ text {akzeptiert w bei}} m_ {j}]}$

Weil der Prover auf der rechten Seite die Nachricht senden könnte m_J+1 um den Ausdruck auf der linken Seite zu maximieren. Und:

$oder Pr \ links [v {\ text {akzeptiert}} w {\ text {startet bei}} m_ {j} \ rechts]}$

Da derselbe Prover es nicht besser abschneiden kann, als dieselbe Nachricht zu senden. So gilt dies, ob i ist gerade oder seltsam und der Beweis dafür IP ⊆ PSPACE ist komplett.

Hier haben wir eine Polynomraummaschine konstruiert, die den besten Prover verwendet P für eine bestimmte Zeichenfolge w in der Sprache A. Wir verwenden diesen besten Prover anstelle eines Provers mit zufälligen Eingangsbits, da wir jeden Satz zufälliger Eingangsbits im Polynomraum ausprobieren können. Da wir ein interaktives Proof -System mit einer Polynomraummaschine simuliert haben, haben wir das gezeigt IP ⊆ PSPACE, wie gewünscht.

PSPACE ⊆ IP

Um die Technik zu veranschaulichen, die verwendet wird, um zu beweisen PSPACE ⊆ IPWir werden zunächst einen schwächeren Satz beweisen, der von Lund et al.: #sat ∈ bewiesen wurde IP. Wenn wir dann die Konzepte aus diesem Beweis verwenden, werden wir es erweitern, um zu zeigen, dass TQBF ∈ IP. Da tqbf ∈ PSPACE-Complete und TQBF ∈ IP dann PSPACE ⊆ IP.

#Sat ist Mitglied von IP

Wir zeigen zunächst, dass #SAT in ist IP, wo:

$oder }}\Rechts\}.}$

Beachten Sie, dass sich dies von der normalen Definition von unterscheidet #SatDa es sich eher um ein Entscheidungsproblem als um eine Funktion handelt.

Zuerst verwenden wir die Arithmetisierung, um die boolesche Formel mit n Variablen, φ (b₁, ..., b_n) zu einem Polynom p_φ(x₁, ..., x_n), wo p_φ nachahmt φ darin p_φ ist 1, wenn φ wahr ist und 0 ansonsten vorgesehen ist, dass die Variablen von p_φ werden boolesche Werte zugewiesen. Die in φ verwendeten Booleschen Operationen ∨, ∧ und ¬ verwendet werden in φ simuliert p_φ Durch das Ersetzen der Operatoren in φ, wie in der folgenden Tabelle gezeigt.

Arithmetisierungsregeln für die Umwandlung einer booleschen Formel φ (b₁, ..., b_n) zu einem Polynom p_φ(x₁, ..., x_n))

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

Als Beispiel φ = a ∧ (b ∨ ¬c) würde wie folgt in ein Polynom umgewandelt werden:

$oder = a \ keil \ links (1- (1-b) (1- (1-c)) \ rechts) \\ & = A \ links (1-b) (1- (1-c))) \ rechts) \\ & = a- (ac-abc) \ end {ausgerichtet}}}$

Die Operationen ab und a ∗ b Jedes führen zu einem Polynom mit einem Grad, der durch die Summe der Grad der Polynome für a und b und daher beträgt der Grad einer Variablen höchstens die Länge von φ.

Nun lass F ein endliches Feld mit Bestellung sein q > 2ⁿ; erfordern auch, dass Q mindestens 1000 sein kann. Für jeweils 0 ≤ i ≤ neine Funktion definieren f_i an FParameter ${\ displayStyle a_ {1}, \ dots, a_ {i-1} \ in f}$und eine einzelne Variable a_i in F: Für 0 ≤ i ≤ n und für ${\ displayStyle a_ {1}, \ dots, a_ {i} \ in f}$ Lassen

${\ displayStyle f_ {i} (a_ {1}, \ dots, a_ {i}) = \ sum \ nolimits _ {a_ {i+1}, \ dots, a_ {n} \ in \ {0,1 \ \ }} p (a_ {1}, \ dots, a_ {n}).}$

Beachten Sie, dass der Wert von f₀ ist die Anzahl der zufriedenstellenden Zuordnungen von φ. f₀ ist eine Hohlraumfunktion ohne Variablen.

Jetzt funktioniert das Protokoll für #SAT wie folgt:

• Phase 0: Der Prover P wählt eine Prime q > 2ⁿ und berechnet f₀, es sendet dann q und f₀ zum Verifizierer V. V Überprüft das q ist eine Prime größer als max (1000, 2ⁿ) und das f₀() = k.
• Phase 1: P sendet die Koeffizienten von f₁(z) als Polynom in z. V überprüft, dass der Grad von f₁ ist weniger als n und das f₀ = f₁(0) + f₁(1). (Wenn nicht V lehnt ab). V Sendet nun eine Zufallszahl r₁ aus F zu P.
• Phase I: P sendet die Koeffizienten von ${\ displayStyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, z)}$ als Polynom in z. V überprüft, dass der Grad von f_i ist weniger als n und das $oder {i} (r_ {1}, \ dots, r_ {i-1}, 1)}$. (Wenn nicht V lehnt ab). V Sendet nun eine Zufallszahl r_i aus F zu P.
• Phase N+1: V bewertet ${\ displayStyle p (r_ {1}, \ dots, r_ {n})}$ mit dem Wert vergleichen ${\ displayStyle f_ {n} (r_ {1}, \ dots, r_ {n})}$. Wenn sie gleich sind V Akzeptiert, sonst V lehnt ab.

Beachten Sie, dass dies ein Public-Coin-Algorithmus ist.

Wenn φ hat k Erfüllende Aufträge klar erfreudig V wird akzeptieren. Wenn φ nicht hat k Befriedigende Aufgaben Wir gehen davon aus, dass es einen Prover gibt ${\ displayStyle {\ tilde {p}}}$ das versucht zu überzeugen V dass φ hat k Befriedigende Aufgaben. Wir zeigen, dass dies nur mit geringer Wahrscheinlichkeit erfolgen kann.

Verhindern V von der Ablehnung in Phase 0,, ${\ displayStyle {\ tilde {p}}}$ muss einen falschen Wert senden ${\ displayStyle {\ tilde {f}} _ {0} ()}$ zu P. Dann in Phase 1,, ${\ displayStyle {\ tilde {p}}}$ muss ein falsches Polynom senden ${\ displayStyle {\ tilde {f}} _ {1}}$ mit der Eigenschaft das $oder$. Wann V wählt einen zufälligen r₁ zu senden an PAnwesend

$oder 2}}}.}$

Dies liegt daran, dass ein Polynom in einer einzigen Variablen von höchsten d kann nicht mehr als haben als d Wurzeln (es sei denn, es bewertet immer 0). Also zwei beliebige Polynome in einer einzelnen Variablen des Grades höchstens d kann nur in gleich sein in d setzt. Da |F| > 2ⁿ die Chancen von r₁ Einer dieser Werte zu sein ist höchstens ${\ displayStyle n/2^{n} <n/n^{3}}$ wenn n > 10 oder höchstens ((n/1000) ≤ (n/n³) wenn n ≤ 10.

Verallgemeinerung dieser Idee für die anderen Phasen, die wir für jedes 1 ≤ haben i ≤ n wenn

$oder {i-1}),}$

dann für r_i zufällig ausgewählt von FAnwesend

$oder ] \ leq {\ tfrac {1} {n^{2}}}.}$

Es gibt n Phasen, also die Wahrscheinlichkeit, dass ${\ displayStyle {\ tilde {p}}}$ hat Glück, weil V wählt irgendwann eine bequeme Auswahl aus r_i ist höchstens 1//n. Daher kann kein Prover den Verifizierer mit einer Wahrscheinlichkeit von mehr als 1//// 1/ akzeptieren lassenn. Wir können auch aus der Definition sehen, dass der Überprüfer V arbeitet in probabilistischer Polynomzeit. Also #sat ∈ IP.

TQBF ist Mitglied von IP

Um das zu zeigen PSPACE ist eine Teilmenge von IPWir müssen a wählen PSPACE-Complete Problem und zeigen, dass es in ist IP. Sobald wir dies zeigen, ist es klar, dass es klar ist PSPACE ⊆ IP. Die hier gezeigte Beweistechnik wird dem zugeschrieben Adi Shamir.

Wir wissen, dass TQBF in ist PSPACE-Complete. Sei ψ ein quantifizierter boolescher Ausdruck:

$oder$

wobei φ eine CNF -Formel ist. Dann Q_i ist ein Quantifizierer, entweder ∃ oder ∀. Jetzt f_i ist dasselbe wie im vorherigen Beweis, aber jetzt enthält es auch Quantifizierer.

$oder mathsf {q}} _ {i+1} x_ {i+1} \ dots {\ mathsf {q}} _ {m} x_ {m} [\ varphi (a_ {1}, \ dots, a_ {i} )] {\ text {ist wahr}} \\ 0 & {\ text {sonst}} \ end {cases}}}$

Hier, φ (a₁, ..., a_i) ist φ mit a₁ zu a_i Ersetzt durch x₁ zu x_i. Daher f₀ ist der Wahrheitswert von ψ. Um ψ zu arithmetisieren, müssen wir die folgenden Regeln verwenden:

$oder \ 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} = \ existiert \ end {cases}}}$

wo wie zuvor wir definieren x ∗ y = 1 - (1 - -x) (1 -y).

Durch die Verwendung der in #SAT beschriebenen Methode müssen wir ein Problem für jeden haben f_i Der Grad des resultierenden Polynoms kann sich bei jedem Quantifizierer verdoppeln. Um dies zu verhindern, müssen wir einen neuen Reduktionsbetreiber einführen R Dies reduziert die Grad des Polynoms, ohne ihr Verhalten auf booleschen Eingaben zu ändern.

Also jetzt, bevor wir arithmetisieren $oder$ Wir führen einen neuen Ausdruck vor:

$oder R} x_ {2} \ dots {\ mathsf {q}} _ {m} \ mathsf {r} x_ {1} \ dots \ mathrm {r} x_ {m} [\ varphi]}$

oder einen anderen Weg einsetzen:

$oder wobei}} {\ mathsf {s}} _ {i} \ in \ {\ forall, \ existiert, \ math mathrm {r} \}, \ y_ {i} \ in \ {x_ {1}, \ dots, x_____________________________________________SNTE {m}\}}$

Nun für jeden i ≤ k Wir definieren die Funktion f_i. Wir definieren auch ${\ displayStyle f_ {k} (x_ {1}, \ dots, x_ {m})}$ das Polynom sein p(x₁, ..., x_m), das durch Arithmetisierung φ erhalten wird. Um den Grad des Polynoms niedrig zu halten, definieren wir nun f_i bezüglich f_i+1:

$oder i+1} (a_ {1}, \ dots, a_ {i}, 0) \ cdot f_ {i+1} (a_ {1}, \ dots, a_ {i}, 1)}$

$oder i+1} (a_ {1}, \ dots, a_ {i}, 0)*f_ {i+1} (a_ {1}, \ dots, a_ {i}, 1)}$

${\ displaystyle {\ text {if}} {\ mathsf {s}} _ {i+1} = \ mathsf {r}, \ quad f_ {i} (a_ {1}, \ dots, a_ {i},, a) = (1-a) f_ {i+1} (a_ {1}, \ dots, a_ {i}, 0)+af_ {i+1} (a_ {1}, \ dots, a_ {i} , 1)}$

Jetzt können wir sehen, dass der Reduktionsoperation R den Grad des Polynoms nicht ändert. Es ist auch wichtig zu sehen, dass der r_x Der Betrieb ändert nicht den Wert der Funktion auf booleschen Eingängen. So f₀ ist immer noch der Wahrheitswert von ψ, aber der r_x Wert erzeugt ein Ergebnis, das linear in ist x. Auch nach allen ${\ displaystyle {\ mathsf {q}} _ {i} x_ {i}}$ Wir fügen hinzu $oder$ in ψ ', um den Grad nach der Arithmetisierung auf 1 zu reduzieren ${\ displayStyle {\ mathsf {q}} _ {i}}$.

Beschreiben wir nun das Protokoll. Wenn n ist die Länge von ψ, alle arithmetischen Operationen im Protokoll sind mindestens über ein Feld der Größe n⁴ wo n ist die Länge von ψ.

• Phase 0: P → V: P sendet f₀ zu V. V Überprüft das f₀= 1 und ablehnt, wenn nicht.
• Phase 1: P → V: P sendet f₁(z) zu V. V Verwendet Koeffizienten zur Bewertung f₁(0) und f₁(1). Dann prüft es, dass der Grad des Polynoms höchstens ist n und dass die folgenden Identitäten wahr sind:

$oder \ forall \\ f_ {1} (0)*f_ {1} (1) & {\ text {if}} {\ mathsf {s}} = \ existiert. \\ (1-r) f_ {1} ( 0)+rf_ {1} (1) & {\ text {if}} {\ mathsf {s}} = \ mathrm {r}. \ End {cases}}}}$

Wenn beides fehlschlägt, lehnen Sie ab.

• Phase I: P → V: P sendet ${\ displayStyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, z)}$ als Polynom in z. r₁ bezeichnet die zuvor festgelegten zufälligen Werte für ${\ displayStyle r_ {1}, \ dots, r_ {i-1}}$

V Verwendet Koeffizienten zur Bewertung ${\ displayStyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, 0)}$ und ${\ displayStyle f_ {i} (r_ {1}, \ dots, r_ {i-1}, 1)}$. Dann prüft es, dass der Polynomgrad höchstens ist n und dass die folgenden Identitäten wahr sind:

${\ displayStyle f_ {i-1} (r_ {1}, \ dots, r_ {i-1}) = {\ begin {case }, 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}} = \ exists. \ end. {Fälle}}}$

$oder } (r_ {1}, \ dots, r_ {i-1}, 1) {\ text {if}} {\ mathsf {s}} = \ mathhrm {r}.}.}.$

Wenn beides fehlschlägt, lehnen Sie ab.

V → P: V wählt zufällig r in F und sendet es an P. (wenn ${\ displayStyle {\ mathsf {s}} = \ mathrm {r}}$ dann das r ersetzt den vorherigen r).

Goto Phase i+1 wo P muss überzeugen V das ${\ displayStyle f_ {i} (r_ {1}, \ dots, r)}$ ist richtig.

• Phase k + 1: V bewertet ${\ displayStyle p (r_ {1}, \ dots, r_ {m})}$. Dann überprüft es, ob ${\ displayStyle p (r_ {1}, \ dots, r_ {m}) = f_ {k} (r_ {1}, \ dots, r_ {m})}$ Wenn sie gleich sind, dann sind V Akzeptiert, sonst V lehnt ab.

Dies ist das Ende der Protokollbeschreibung.

Wenn ψ wahr ist, dann V wird akzeptieren, wann P folgt dem Protokoll. Ebenso wenn ${\ displayStyle {\ tilde {p}}}$ ist ein böswilliger Prover, der liegt, und wenn ψ falsch ist, dann ist dann ${\ displayStyle {\ tilde {p}}}$ muss in Phase 0 liegen und einen Wert für einen Wert senden für f₀. Wenn in Phase i, V hat einen falschen Wert für ${\ displayStyle f_ {i-1} (r_ {1}, \ dots)}$ dann ${\ displayStyle f_ {i} (r_ {1}, \ dots, 0)}$ und ${\ displayStyle f_ {i} (r_ {1}, \ dots, 1)}$ wird wahrscheinlich auch falsch sein und so weiter. Die Wahrscheinlichkeit für ${\ displayStyle {\ tilde {p}}}$ um zufälliges Glück zu haben r ist höchstens der Grad des Polynoms geteilt durch die Feldgröße: ${\ displayStyle n/n^{4}}$. Das Protokoll läuft durch O(n²) Phasen, so die Wahrscheinlichkeit, dass ${\ displayStyle {\ tilde {p}}}$ hat in einer Phase Glück und ist ≤ 1//n. Wenn ${\ displayStyle {\ tilde {p}}}$ ist dann nie Glück V wird in der Phase ablehnen k+1.

Da haben wir jetzt gezeigt IP ⊆ PSPACE und PSPACE ⊆ IP, können wir schließen, dass IP = PSPACE wie gewünscht. Darüber hinaus haben wir gezeigt, dass alle IP Der Algorithmus kann seit der Reduzierung von öffentlich-garantiert werden PSPACE zu IP hat diese Eigenschaft.

Varianten

Es gibt eine Reihe von Varianten von IP die die Definition des interaktiven Proof -Systems geringfügig ändern. Wir fassen hier einige der bekanntesten hier zusammen.

tauchen

Eine Teilmenge von IP ist der Deterministischer interaktiver Beweis Klasse, die ähnlich ist wie IP hat aber einen deterministischen Überprüfung (d. H. Ohne Zufälligkeit). Diese Klasse ist gleich Np.

Perfekte Vollständigkeit

Ein Äquivalent Definition von IP Ersetzt die Bedingung, dass die Wechselwirkung mit hoher Wahrscheinlichkeit für Zeichenfolgen in der Sprache mit der Anforderung gelten, dass sie stets gelingt es:

${\ displayStyle w \ in l \ rightarrow \ pr [v \ leftrightarrow p {\ text {akzeptiert}} w] = 1}$

Dieses scheinbar stärkere Kriterium für "perfekte Vollständigkeit" verändert die Komplexitätsklasse nicht IPDa jede Sprache mit einem interaktiven Proof -System ein interaktives Proof -System mit perfekter Vollständigkeit erhalten kann.^[4]

MIP

1988 haben Goldwasser et al. erstellte ein noch leistungsstärkeres interaktives Proof -System basierend auf IP genannt MIP in dem es gibt zwei unabhängige Provers. Die beiden Provers können nicht kommunizieren, sobald der Überprüfer damit begonnen hat, Nachrichten an sie zu senden. So wie es einfacher zu erkennen ist, ob ein Verbrecher lügt, wenn er und sein Partner in getrennten Räumen verhört werden, ist es erheblich einfacher, einen böswilligen Prover zu erkennen, der versucht, den Überprüfer auszutricksen, wenn es einen anderen Prover gibt, mit dem er sich verprügeln kann. Tatsächlich ist dies so hilfreich, dass Babai, Fortnow und Lund das zeigen konnten MIP = Nexptime, die Klasse aller Probleme lösbar durch a Nichtdeterministisch Maschine in Exponentialzeit, eine sehr große Klasse. Darüber hinaus alle Sprachen in Np Null-Wissen-Beweise in einem haben MIP System, ohne zusätzliche Annahmen; Dies ist nur für bekannt IP unter der Annahme der Existenz von Einwegfunktionen.

Ipp

Ipp (Unbegrenzte IP) ist eine Variante von IP wo wir das ersetzen BPP Prüfer von a Pp Überprüfung. Genauer gesagt ändern wir die Vollständigkeits- und Klangbedingungen wie folgt:

• Vollständigkeit: Wenn sich eine Zeichenfolge in der Sprache befindet, wird der ehrliche Überprüfer von dieser Tatsache von einem ehrlichen Prover mit einer Wahrscheinlichkeit von mindestens 1/2 überzeugt.
• Solidität: Wenn sich die Zeichenfolge nicht in der Sprache befindet, kann kein Prover den ehrlichen Überprüfer davon überzeugen, dass er in der Sprache liegt, außer mit einer Wahrscheinlichkeit von weniger als 1/2.

Obwohl Ipp auch gleich PSPACE, Ipp Protokolle verhalten sich ganz anders als IP in Gedenken an Orakel: Ipp=PSPACE in Bezug auf alle Orakel während IP ≠ PSPACE in Bezug auf fast alle Orakel.^[5]

QIP

QIP ist eine Version von IP Ersetzen des BPP Prüfer von a BQP Verifier, wo BQP ist die Klasse von Problemen lösbar durch Quantencomputer in Polynomzeit. Die Nachrichten bestehen aus Qubits.^[6] Im Jahr 2009 bewiesen Jain, Ji, Upadhyay und Watrous das QIP auch gleich PSPACE,^[7] Dies impliziert, dass diese Änderung dem Protokoll keine zusätzliche Leistung verleiht. Dies füllt ein früheres Ergebnis von Kitaev und Watrous, das QIP ist in Nachfolger Weil QIP = QIP[3], so dass mehr als drei Runden nie notwendig sind.^[8]

Kompip

Wohingegen Ipp und QIP dem Verifizierer mehr Kraft geben, a Kompip System (wettbewerbsfähiges IP -Proof -System) schwächt den Vollständigkeitszustand auf eine Weise, die den Prover schwächt:

• Vollständigkeit: Wenn eine Zeichenfolge in der Sprache ist LDer ehrliche Überprüfer wird von dieser Tatsache von einem ehrlichen Prover mit einer Wahrscheinlichkeit von mindestens 2/3 überzeugt. Darüber hinaus wird der Prover dies in der probabilistischen Polynomzeit erweisen, die Zugriff auf ein Orakel für die Sprache L.

Dies macht den Prover im Wesentlichen a BPP Maschine mit Zugriff auf ein Orakel für die Sprache, jedoch nur im Vollständigkeitsfall, nicht im Fall von Soundness. Das Konzept ist, dass wenn eine Sprache in ist Kompipund dann interaktiv zu beweisen, dass es in gewissem Sinne so einfach ist wie die Entscheidung. Mit dem Oracle kann der Prover das Problem leicht lösen, aber seine begrenzte Kraft macht es viel schwieriger, den Überprüfer von irgendetwas zu überzeugen. In der Tat, Kompip ist nicht einmal bekannt oder angenommen, dass sie enthalten Np.

Andererseits kann ein solches System einige Probleme lösen, von denen angenommen wird, dass sie schwer sind. Etwas paradoxerweise, obwohl ein solches System nicht in der Lage ist, alle zu lösen Np, es kann leicht alle lösen NP-Complete Probleme aufgrund der Selbstreduzierbarkeit. Dies beruht auf der Tatsache, dass, wenn die Sprache L nicht ist Np-Hard ist der Prover wesentlich eingeschränkt (da er nicht mehr über alle entscheiden kann Np Probleme mit seinem Orakel).

Zusätzlich die Graph Nichtisomorphismus -Problem (Das ist ein klassisches Problem in IP) ist auch in KompipDa der einzige harte Betrieb der Prover durchführen muss, ist Isomorphismus -Tests, mit dem das Orakel gelöst werden kann. Quadratische Nichtanmieter und Graph-Isomorphismus sind ebenfalls in Kompip.^[9] Beachten Sie, quadratische Nicht-Residuosity (QNR) ist wahrscheinlich ein einfacheres Problem als das Graph-Isomorphismus, wenn QNR in ist HOCH schneiden Coup.^[10]

Anmerkungen

Verweise

• Babai, L. Handelsgruppentheorie für Zufälligkeit. In Proceedings of the 17. ACM -Symposium zur Berechnungstheorie. ACM, New York, 1985, S. 421–429.
• SHAFI GOLDSER, Silvio Micali, und Charles Rackoff. Die Wissenskomplexität interaktiver Proof-Systeme. Verfahren des 17. ACM -Symposiums zur Theorie der Berechnung, Providence, Rhode Island. 1985, S. 291–304. Erweiterte Zusammenfassung
• Shafi Goldwasser und Michael Sipser. Private Münzen gegen öffentliche Münzen in interaktiven Proof -Systemen. Verfahren des 18. jährlichen ACM -Symposiums zur Berechnungstheorie. ACM, New York, 1986, S. 59–68.
• Rahul Jain, Zhengfeng JI, Sarvagya Upadhyay, John Watrous. QIP = PSPACE. [1]
• Lund, C., Fortnow, L., Karloff, H.,, Nisan, N. Algebraische Methoden für interaktive Proof -Systeme. In Proceedings of 31st Symposium über die Grundlagen der Informatik. IEEE, New York, 1990, S. 2–90.
• Adi Shamir. IP = PSPACE. Journal of the ACM, Band 39, Ausgabe 4, p. 869–877. Oktober 1992.
• Alexander Shen. IP = PSPACE: Vereinfachter Beweis. J.acm, v. 39 (4), S. 878–880, 1992.
• Komplexitätszoo: IP, MIP, Ipp, QIP, QIP (2), Kompip, Frip