Можно ли использовать случайные ограничения для получения нижней границы для

13

Существует несколько хорошо известных результатов оценки нижнего предела размера схемы основанных на случайных ограничениях и лемме о переключении .AC0

Можем ли мы разработать результат леммы о переключении, чтобы доказать нижнюю оценку размера для цепей (аналогично нижним оценкам для )? A C 0TC0AC0

Или есть какое-то существенное препятствие для использования этого подхода для доказательства нижних границ ?TC0

Говорят ли какие-либо барьерные результаты, такие как Natural Proofs , об использовании методов, подобных лемме о переключении, для доказательства нижних границ?TC0

Jeigh
источник
Вы знакомы с доказательством переключения леммы для ? AC0
Каве
1
Я прочитал главу о нижних границах учебника Арора. Во-первых, преобразуйте любой контур постоянной глубины в схему без вентилей НЕ с чередованием слоев И-ИЛИ, а во-вторых, используя лемму переключения, переключите эти два слоя, в конце концов мы получим верхнюю часть схемы, а второй уровень - это те же вентили И (или ИЛИ) таким образом, мы можем лишить схему одного слоя, перерисовав глубину контура.
Jeigh
1
Тем не менее, это не проще, чем логический случай, чтобы наблюдать вывод гейта, когда мы фиксируем несколько значений входов (в логическом случае мы фиксируем около квадратного корня n входов). И ворота, и ИЛИ ворота - это экстремальный вариант ворот порога и очень легко наблюдать влияние ограничений.
Jeigh
2
Идея техники случайных ограничений заключается в том, что попадание в результате случайного ограничения становится проще (фактически постоянным) с ненулевой вероятностью при сохранении достаточного количества свободных переменных. В отличие от и ворот, одинAC0 ворота, пораженные случайным ограничением, все равно вычисляютmodp ворота на входах меньшего размера и не станет проще. modp
Каве
Отметим также, что случайные ограничения и лемма о переключении являются одним из основных примеров естественных доказательств. В любом случае, надеюсь, эксперт по сложности схем выложит более полный ответ. PS: Я взял на себя смелость переписать вопрос, не стесняйтесь отменить, если вам не нравится мое редактирование.
Каве

Ответы:

11

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

В частности, в статье « Соотношение размера и глубины для пороговых цепей» Impagliazzo, Paturi и Saks используют случайные ограничения, чтобы доказать нижнюю границу суперлайнера (по числу проводов) для цепей пороговых значений постоянной глубины, вычисляя функцию четности.

TC0TC0

Кристоффер Арнсфельт Хансен
источник
6

См. Также недавнюю работу Дэниэла Кейна и Райана Уильямса, Нижние границы суперлинейных затворов и суперквадратичных проводов для пороговых цепей глубины 2 и 3 (STOC 2016).

Райан описывает статью следующим образом (следующее описание взято с его домашней страницы):

Мы даем явную функцию в для которой каждому большинству линейных пороговых схем глубины два (с неограниченными весами) нужно около nPPn1.5n2.5O(n)

Юваль Фильмус
источник