Tak naprawdę istnieje tylko jedna „sztandarowa” technika nierelatywizująca: mianowicie arytmetyzacja (technika stosowana w dowodach IP = PSPACE, MIP = NEXP, PP⊄SIZE (n k ), MA EXP ⊄P / poly i kilka innych wyników ).
Jednak dowód, że wszystkie języki NP mają obliczeniowe dowody zerowej wiedzy (zakładając, że istnieją funkcje jednokierunkowe), dzięki Goldreichowi, Micali i Wigdersonowi, zastosował inną technikę nierelatywistyczną (mianowicie symetrie problemu 3-COLORING ).
Arora, Impagliazzo i Vazirani argumentowali, że nawet „lokalna sprawdzalność”, właściwość problemów NP-zupełnych zastosowanych w dowodzie oryginalnego twierdzenia Cooka-Levina (a także twierdzenia PCP), powinna być liczona jako technika nierelatywizująca ( chociaż Lance Fortnow napisał artykuł, w którym argumentował coś przeciwnego). Kwestią sporną jest to, czy sensowne jest relatywizowanie klasy złożoności „problemów, które można sprawdzić lokalnie”.
Argumenty kamykowe wykorzystane w wynikach z lat 70. XX wieku, takie jak CZAS (n) ≠ NTIME (n), zostały przedstawione jako kolejny przykład techniki nierelatywizacyjnej.
Aby uzyskać więcej informacji, możesz sprawdzić mój dokument algebryzacyjny z Wigdersonem , a zwłaszcza zawarte w nim odniesienia. Musieliśmy właściwie skatalogować istniejące techniki nierelatywizujące, aby dowiedzieć się, które z nich były i nie były objęte barierą algebriacji.
Dodatek: Właśnie zdałem sobie sprawę, że zapomniałem wspomnieć o obliczeniach kwantowych opartych na pomiarach (MBQC) , które ostatnio zostały świetnie wykorzystane przez Broadbent, Fitzsimons i Kashefi do uzyskania twierdzeń o kwantowej złożoności (takich jak QMIP = MIP * i BQP = MIP z uwikłanymi dowodami BQP i weryfikatorem BPP), które najprawdopodobniej nie zostaną relatywizowane.