Чем интересны ворота mod

39

Райан Уильямс только что опубликовал свою нижнюю границу для ACC , класса задач, которые имеют контуры постоянной глубины с неограниченным разветвлением и вентилями AND, OR, NOT и MOD_m для всех возможных m.

Что особенного в воротах MOD_m?

Они позволяют имитировать арифметику над любым кольцом Z_m.
Перед результатом Райана, бросая ворота микса MOD_m в первый класс, для которого не работали известные нижние границы.

Есть ли другая естественная причина для изучения ворот MOD_m?

cc.complexity-theory circuit-complexity big-picture circuit-families Дана Мошковиц
источник

39

$ACC^0$ - класс естественной сложности.

1) Баррингтон показал, что вычисления над неразрешимыми моноидами захватывают $NC^1$ то время как над разрешимыми моноидами захватывают $ACC^0$ .

2) В последнее время Хансен и Куки доказали прекрасный результат, что программы плоского ветвления разной ширины с постоянными размерами в точности равны $ACC^0$ . Без условия планарности мы, конечно, получаем результат Баррингтона, характеризующий $NC^1$ .

Таким образом, разница между и является теоретико-групповой с одной стороны и топологической с другой. $ACC^0$ $NC^1$

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

Что касается планарности, хотелось бы полагать, что планарность может налагать ограничения / узкие места в потоке информации. Это не всегда верно: например, известно, что вариации плоского 3SAT являются NP-полными. Однако в небольших классах эти ограничения более «вероятны».

В том же духе Вигдерсон показал NL / poly = UL / poly с использованием леммы об изоляции. Мы не знаем, как дерандомизировать лемму об изоляции над произвольными группами DAG, чтобы получить NL = UL, но мы знаем, как это сделать для плоских групп DAG.

V Vinay
источник

1

Большое спасибо за информацию! Я хотел бы услышать больше об интуиции для этих результатов. Что касается моего вопроса: ваш аргумент в основном состоит в том, что глубина

[O (log n), gates AND, OR, NOT] является естественной, и

является ее небольшим изменением (для разрешимых, а не неразрешимых моноидов). или планарные, а не неплоские программы ветвления). Не могли бы вы уточнить немного: привести примеры интересных моноидов для вычислений, и как их разрешающая способность имеет значение? Есть ли априорная мотивация интересоваться, является ли программа ветвления плоской или нет?

N C^{1}

$NC^1$

A C C

$ACC$

Дана Мошковиц

7

A C^{0}

$AC^0$

A C^{0}

$AC^0$

@ Vinay: Вы уверены, что результат NL / poly = UL / poly связан с Вигдерсоном?

Дай Ле

17

$\bmod m$ $m$ $\bmod p$

Рассмотрим класс контуров постоянной глубины, которые состоят только из элементов , а также входов и констант на листьях. Тогда можно легко показать, что функция ИЛИ (например) не может быть вычислена такими схемами, независимо от размера схемы. (Это потому, что любая такая схема вычисляет полином низкой степени над , а степень OR равна ). $\bmod p$ $\mathbb{F}_p$ $n$

Однако, если мы рассмотрим схемы, состоящие только из элементов которых имеет по крайней мере два различных простых множителя, для функции ИЛИ существует схема глубины (экспоненциального размера). $\bmod m$ $m$ $2$

И до результата Райана был, я думаю, самым маленьким классом, для которого у нас не было приличных нижних границ. $AC^0[\bmod 6]$

Ramprasad
источник

1

Добавление к последнему предложению: уже было известно, что для вычисления с использованием схем постоянной глубины с использованием вентилей AND, OR, NOT и для простых чисел требуется экспоненциальное число вентилей. (Существует также расширение для относительно простых композитов.) Поскольку 6 - это наименьший композит из двух различных простых чисел, - это "самая простая" функция для вычисления, для которой не было известно экспоненциальной нижней границы.

M O D_{q}

$MOD_q$

M O D_{p}

$MOD_p$

p \neq q

$p \ne q$

M O D_{6}

$MOD_6$

Даниэль Апон

14

Просто чтобы уточнить ваши два момента:

Если мы занимаемся пониманием вычислений, модульный подсчет является одним из рубежей нашего понимания. Модульный счет является одним из самых простых и естественных явлений в вычислениях, но мы, кажется, так мало понимаем в этом. Мы не можем исключить возможность того, что схемы глубины 3 полиномиального размера только с вентилями Mod6 могут вычислять каждую функцию в NP. Предполагается, однако, что такие схемы могут вычислять только функции с большим размером поддержки и, следовательно, не могут вычислять очень простую функцию, такую как AND. На верхней грани ситуация аналогична, у нас нет нетривиальных результатов.

Эти вопросы также очень интересны с чисто математической точки зрения, поскольку они тесно связаны с очень естественными вопросами о полиномах и матрицах над Z_m. Чтобы привести один пример, у нас нет хороших нижних оценок для ранга nxn-диагональной матрицы над Z_6. Кодиагональная матрица имеет 0s на диагонали и ненулевые от диагонали.

Aada
источник

Те, кто интересуется принципом «простое и составное по модулю», должны посетить домашнюю страницу Винса Гролмуса: grolmusz.pitgroup.org

Stasys

Чем интересны ворота mod_m?

Ответы: