Существуют ли канонические нерелятивизирующие методы?

Во многих областях есть канонические методы, которые должен освоить каждый, кто работает в этой области. Например, для сокращения пространства журналов «битовый трюк» для композиции состоит в том, чтобы не создавать полный вывод составной функции, а всегда запрашивать пересчет результата для каждого бита вывода, позволяя сохранить ограничения пространства журнала.

Мой вопрос о нерелятивистских методах. Теоретики обрисовали в общих чертах некоторые фундаментальные нерелятивизирующие операции, или есть различный прием для каждого известного нерелятивизирующего доказательства?

На самом деле существует только один «флагманский» нерелятивизирующий метод: арифметизация (метод, используемый в доказательствах: IP = PSPACE, MIP = NEXP, PP⊄SIZE (n ^k ), MA _EXP ⊄P / poly и ряд других результатов. ).

Однако доказательство того, что все языки NP имеют вычислительные доказательства с нулевым знанием (при условии, что существуют односторонние функции), благодаря Голдрайху, Микали и Вигдерсону, использовало другую нерелятивизирующую технику (а именно, симметрии задачи 3-ЦВЕТА) ).

Арора, Импальяццо и Вазирани утверждали, что даже «локальная проверяемость», свойство NP-полных задач, использованное при доказательстве исходной теоремы Кука-Левина (а также теоремы PCP), должна считаться нерелятивизирующей техникой ( хотя Лэнс Фортноу написал статью, утверждая обратное). Камнем преткновения является то, имеет ли смысл релятивизировать класс сложности «локально проверяемых задач».

Аргументы pebbling, использованные в результатах 1970-х годов, таких как TIME (n) ≠ NTIME (n), были выдвинуты в качестве еще одного примера нерелятивизирующего метода.

Для получения дополнительной информации, возможно, вы захотите проверить мою статью по алгебре с Вигдерсоном , и особенно ссылки в ней. Нам пришлось в значительной степени каталогизировать существующие нерелятивизирующие методы, чтобы выяснить, какие из них были и не были охвачены барьером алгебраизации.

Приложение: Я только что понял, что забыл упомянуть квантовые вычисления, основанные на измерениях (MBQC) , которые недавно были использованы Бродбентом, Фицсимонсом и Кашефи для получения теорем квантовой сложности (таких как QMIP = MIP * и BQP = MIP). с запутанными BQP-пруверами и верификатором BPP), которые, скорее всего, не могут быть релятивизированы.