Ссылки на нижние границы цепей

21

преамбула

Интерактивные системы доказательства и протоколы Артура-Мерлина были введены Голдвассером, Микали, Ракоффом и Бабаем еще в 1985 году. Сначала считалось, что первый более мощный, чем второй, но Голдвассер и Сипсер показали, что они обладают одинаковой силой ( в отношении признания языка). Следовательно, в этом посте я использовал эти два понятия взаимозаменяемо.

Пусть будет классом языков, допускающих интерактивную систему доказательства с раундами. Бабай доказал , что . (Релятивизируемый результат.)k I P [ O ( 1 ) ] Π P 2яп[К]Кяп[О(1)]Π2п

Сначала было неизвестно, может ли неограниченное количество раундов увеличить мощность IP. В частности, было показано, что противоречивые Релятивизации: Fortnow , и Sipser , показали , что в течение некоторого оракула , это имеет место , что . (Следовательно, относительно , не является суперклассом .)A Я Р [ р о л у ] Р НсоNпAяп[поLY]AAяп[поLY]пЧАС

С другой стороны, следующая статья:

Aiello, W., Goldwasser, S., and Hastad, J. 1986. On the power of interaction. In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (October 27 - 29, 1986). SFCS. IEEE Computer Society, Washington, DC, 368-379. DOI= http://dx.doi.org/10.1109/SFCS.1986.36

показывает , что для некоторого оракула , мы имеем . (Следовательно, поскольку, как указано выше, последний является подклассом .)я Р [ р о л у ] ВР Н Б Я Р [ р о л у ] ВЯ Р [ О ( 1 ) ] В Π Р , В 2Вяп[поLY]ВпЧАСВяп[поLY]Вяп[О(1)]ВΠ2п,В


Вопрос

В работе Айелло, Гольдвейзера и Хастада (цитируется выше) говорится:

Используемые методы являются продолжением методов доказательства нижних границ на схемах с малой глубиной, используемых в [FSS], [Y] и [H1].

где [FSS], [Y] и [H1] являются:

[FSS] Furst M., Saxe J. and Sipser M., "Parity, Circuits, and the Polynomial Time Hierarchy," Proceedings 22nd Annual IEEE Symposium on Foundations of Computer Science, 1981, 260-270.

[Y] Yao A. "Separating the Polynomial-Time Hierarchy by Oracles," Proceedings of 6th Annual IEEE Symposium on Foundations of Computer Science, 1985, 1-10.

[H1] Hastad J. "Almost optimal lower bounds for small depth circuits," Proceedings of 18th Annual ACM Symposium on Theory of Computing, 1986, 6-20.

Я нашел бумаги очень старыми и чрезвычайно трудными для подражания. Я прочитал главу 14 книги Ароры и Барака , но, видимо, она не охватывает всего, что мне нужно.

Какие ссылки на «Нижние границы контура» вы предлагаете?

(Мне особенно нужны обзоры, подобные опросам; те, которые новее и не требуют большого опыта, более предпочтительны.)

М.С. Дусти
источник
2
Еще одна ссылка: лекционные заметки Ави Вигдерсона о нижних границах для постоянной глубины и монотонных схем (эта ссылка взята с чернового сайта Арора-Барак).
Алессандро Косентино

Ответы:

14

То, что вы хотите, является хорошим справочным материалом для понимания экспоненциальных нижних границ для цепей вычисляющих функцию PARITY.AС0

Теперь вы не указали, хотите ли вы на самом деле понять доказательство или просто понять вещи на высоком уровне, каким образом в статье об опросе можно будет что-то объяснить.

Недавно я прочитал и полюбил обзорную статью « Сложность конечных функций » Боппаны и Сипсера.

Если вы действительно хотите сесть и понять доказательства, то вы можете либо прочитать доказательства, основанные на лемме о переключении (которые появляются в цитируемых вами работах - [FSS], [Y] и [H1]), либо Разборова-Смоленского доказательство.

Для доказательств с использованием леммы о переключении, доктор Хостад Тезис хорошо читается, если его трудно понять, если вы новичок в этой области. Лучшее изложение доказательства - «Введение в сложность схем и руководство к доказательству Хостада» Аллана Хейдона. Единственная проблема в том, что я не могу найти его в Интернете, и у меня есть бумажная копия. Я действительно рекомендую это, если вы новичок в сложности схемы.

Для подхода Разборова-Смоленского, просто гуглите, и вы получите кучу лекционных заметок. Я понял нижнюю границу этих трех конспектов: Санджив Арора , Мадху Судан и Кристофер Арнсфельт Хансен .

Робин Котари
источник
Вы предлагаете какой-либо способ получить копию изложения доказательства Аллана Хейдона?
MS Dousti
@ Садек: Понятия не имею. Я получил это из моей библиотеки. Он указан на странице технических отчетов CMU ( cs.cmu.edu/~clamen/reports/1990.html ) в виде технического отчета как CMU-CS-90-141, но нет ссылки для его загрузки или поиска в Интернете. Вы можете попробовать написать автору по электронной почте.
Робин Котари
1
Я наконец-то получил ссылку на технический отчет Аллана Хейдона о репозитории CMU .
MS Dousti
14

Если вы находите изложение леммы о переключении в тезисе Хастада трудным для понимания, вы можете попробовать «Учебник по лемме переключения» Пола Бима , который имеет другую версию из-за Разборова (который также явно использует деревья решений, что очень важно в некоторых приложениях леммы о переключении)

Srikanth
источник
14

Эта книга отлично подходит для объяснения нижних границ, если у вас есть доступ к ней.

Введение в сложность цепей Гериберта Фольмера.

Я только что закончил читать, и хотя там говорится, что «введение» - это очень глубокий анализ сложности схемы. Он подробно объясняет все (наиболее популярные) методы доказательства нижних границ схемы в главе 3.

Маркос Вильягра
источник
12

Более свежая ссылка была бы на сложность булевых функций Стасиса Юкны. Вам просто нужно отправить ему электронное письмо или заполнить форму, чтобы получить pdf проекта.

Более старый, но все же хороший справочник - обзор Сложности конечных функций, проведенный Боппаной и Сипсером. Этот опрос очень читабелен по сравнению с другими источниками.

Другой хороший справочник - книга Булевых функций и вычислительных моделей Клота и Кранакиса.

Дай Ле
источник