Gibt es kanonische nicht-relativierende Techniken?

In vielen Bereichen gibt es kanonische Techniken, die jeder auf dem Gebiet beherrschen sollte. Zum Beispiel besteht der "Bit-Trick" für die Komposition bei der Reduzierung des Protokollbereichs darin, nicht die vollständige Ausgabe der zusammengesetzten Funktion zu konstruieren, sondern immer das Ergebnis für jedes Bit der Ausgabe neu zu berechnen, um die Protokollbereichseinschränkungen beizubehalten.

Meine Frage betrifft nicht-relativierende Techniken. Haben die Theoretiker einige grundlegende nicht-relativierende Operationen skizziert oder gibt es für jeden bekannten nicht-relativierenden Beweis einen anderen Trick?

Es gibt wirklich nur eine "Flaggschiff" non-Relativierung Technik , nämlich Arithmetisierung (die verwendete Technik in den Beweisen von IP = PSPACE, MIP = nexp, PP⊄SIZE (n ^k ), MA _EXP ⊄P / Poly und einige anderen Ergebnisse ).

Der von Goldreich, Micali und Wigderson ausgeführte Beweis, dass alle NP-Sprachen rechnergestützte Null-Wissens-Beweise haben (vorausgesetzt, es existieren Einwegfunktionen), verwendete eine andere nicht-relativierende Technik (nämlich die Symmetrien des 3-FARBEN-Problems) ).

Arora, Impagliazzo und Vazirani argumentierten, dass selbst "lokale Überprüfbarkeit", die Eigenschaft von NP-vollständigen Problemen, die im Beweis des ursprünglichen Cook-Levin-Theorems (sowie des PCP-Theorems) verwendet wurden, als nicht relativierende Technik gelten sollte ( obwohl Lance Fortnow einen Artikel verfasst hat, in dem das Gegenteil argumentiert wird. Der springende Punkt ist, ob es sinnvoll ist, die Komplexitätsklasse der "lokal überprüfbaren Probleme" zu relativieren.

Die Kieselargumente, die in Ergebnissen aus den 1970er Jahren wie TIME (n) ≠ NTIME (n) verwendet wurden, wurden als ein weiteres Beispiel für eine nicht relativierende Technik angeführt.

Weitere Informationen finden Sie in meinem Algebrisierungspapier mit Wigderson und insbesondere in den darin enthaltenen Referenzen. Wir mussten die vorhandenen nicht-relativierenden Techniken ziemlich genau katalogisieren, um herauszufinden, welche von der Algebrisierungsbarriere erfasst wurden und welche nicht.

Nachtrag: Mir ist gerade aufgefallen , dass ich vergessen habe, MBQC (Measurement-based Quantum Computing) zu erwähnen , das kürzlich von Broadbent, Fitzsimons und Kashefi in großem Umfang eingesetzt wurde , um Quantenkomplexitätssätze (wie QMIP = MIP * und BQP = MIP) zu erhalten mit verwickelten BQP-Prüfern und BPP-Prüfern), die höchstwahrscheinlich nicht relativiert werden können.