Czy istnieją kanoniczne techniki nierelatywizujące?

W wielu domenach istnieją techniki kanoniczne, które każdy specjalista w tej dziedzinie powinien opanować. Na przykład, w przypadku redukcji przestrzeni logicznej, „sztuczka bitowa” dla kompozycji polega na tym, że nie konstruuje się pełnego wyniku złożonej funkcji, ale zawsze prosi o ponowne obliczenie wyniku dla każdego bitu wyjściowego, co pozwala zachować ograniczenia przestrzeni logowej.

Moje pytanie dotyczy technik nierelatywizujących. Czy teoretycy nakreślili pewne podstawowe operacje nierelatywizujące, czy też istnieje inna sztuczka dla każdego znanego dowodu nierelatywizującego?

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.