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

Существует несколько хорошо известных результатов оценки нижнего предела размера схемы основанных на случайных ограничениях и лемме о переключении . $\mathsf{AC^0}$

Можем ли мы разработать результат леммы о переключении, чтобы доказать нижнюю оценку размера для цепей (аналогично нижним оценкам для )? $\mathsf{TC^0}$ $\mathsf{AC^0}$

Или есть какое-то существенное препятствие для использования этого подхода для доказательства нижних границ ? $\mathsf{TC^0}$

Говорят ли какие-либо барьерные результаты, такие как Natural Proofs , об использовании методов, подобных лемме о переключении, для доказательства нижних границ? $\mathsf{TC^0}$

cc.complexity-theory circuit-complexity lower-bounds boolean-functions Jeigh
источник

Вы знакомы с доказательством переключения леммы для

A C^{0}

$\mathsf{AC^0}$

Каве

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

Jeigh

Тем не менее, это не проще, чем логический случай, чтобы наблюдать вывод гейта, когда мы фиксируем несколько значений входов (в логическом случае мы фиксируем около квадратного корня n входов). И ворота, и ИЛИ ворота - это экстремальный вариант ворот порога и очень легко наблюдать влияние ограничений.

Jeigh

Идея техники случайных ограничений заключается в том, что попадание

в результате случайного ограничения становится проще (фактически постоянным) с ненулевой вероятностью при сохранении достаточного количества свободных переменных. В отличие от

ворот, один

A C^{0}

$\mathsf{AC^0}$

\land

$\land$

\lor

$\lor$

ворота, пораженные случайным ограничением, все равно вычисляют

\mod p

$\mod p$

ворота на входах меньшего размера и не станет проще.

\mod p

$\mod p$

Каве

Отметим также, что случайные ограничения и лемма о переключении являются одним из основных примеров естественных доказательств. В любом случае, надеюсь, эксперт по сложности схем выложит более полный ответ. PS: Я взял на себя смелость переписать вопрос, не стесняйтесь отменить, если вам не нравится мое редактирование.

Каве

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

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

Мы даем явную функцию в для которой каждому большинству линейных пороговых схем глубины два (с неограниченными весами) нужно около $\mathsf{PP}$ $n^{1.5}$ $n^{2.5}$ $O(n)$

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

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

Ответы: