Apakah ada teknik non-relativizing kanonik?

Dalam banyak domain, ada teknik kanonik yang harus dikuasai semua orang di bidang ini. Misalnya, untuk pengurangan logspace, "trik bit" untuk komposisi yang terdiri dari tidak membangun output penuh dari fungsi yang dikomposisikan, tetapi selalu meminta untuk menghitung ulang hasil untuk setiap bit output, yang memungkinkan untuk menjaga batasan logspace.

Pertanyaan saya adalah tentang teknik non-relativizing. Apakah para ahli teori telah menguraikan beberapa operasi mendasar non-relativizing, atau adakah trik yang berbeda untuk setiap bukti non-relativizing yang diketahui?

Ada benar-benar hanya satu "flagship" teknik non-merelatifkan: yaitu, arithmetization (teknik yang digunakan dalam bukti IP = PSPACE, MIP = NEXP, PP⊄SIZE (n ^k ), MA _EXP ⊄P / poli, dan beberapa hasil lainnya ).

Namun, bukti bahwa semua bahasa NP memiliki bukti nol-pengetahuan komputasi (dengan asumsi fungsi satu arah ada), karena Goldreich, Micali, dan Wigderson, menggunakan teknik non-relativizing berbeda (yaitu, simetri dari masalah 3-WARNA) ).

Arora, Impagliazzo, dan Vazirani berpendapat bahwa bahkan "pemeriksaan lokal," properti masalah NP-lengkap yang digunakan dalam bukti Teorema Cook-Levin asli (serta Teorema PCP), harus dihitung sebagai teknik non-relativizing ( meskipun Lance Fortnow menulis makalah dengan alasan sebaliknya). Poin penting adalah apakah masuk akal untuk merelatifkan kelas kompleksitas "masalah yang bisa diperiksa secara lokal."

Argumen kerikil yang digunakan dalam hasil dari tahun 1970-an seperti TIME (n) ≠ NTIME (n) telah diajukan sebagai contoh lain dari teknik non-relativizing.

Untuk lebih lanjut, Anda mungkin ingin memeriksa kertas algebrization saya dengan Wigderson , dan terutama referensi di dalamnya. Kami harus cukup katalog teknik non-relativizing yang ada untuk mencari tahu mana yang dan tidak tercakup oleh penghalang algebrization.

Tambahan: Saya baru menyadari bahwa saya lupa menyebutkan komputasi kuantum berbasis pengukuran (MBQC) , yang baru-baru ini digunakan untuk efek hebat oleh Broadbent, Fitzsimons, dan Kashefi untuk mendapatkan teorema kompleksitas kuantum (seperti QMIP = MIP *, dan BQP = MIP dengan BQP provers terjerat dan verifier BPP) yang kemungkinan besar gagal untuk merelatifikasi.