Какие

Знаменитая картина мира Нила Иммермана выглядит следующим образом (нажмите, чтобы увеличить):

Его «действительно выполнимый» класс не включает другого класса; мой вопрос тогда:

Что такое проблема AC ^0, которая считается непрактичной и почему?

cc.complexity-theory circuit-complexity Михаэль Кадилхак
источник

Возможно проблема, которая требует схем глубины 10 ^ {10 ^ 100}?

Цуёси Ито

@ Росс: Я так не думаю, потому что он не упомянул «реальный мир» и спросил «почему»; Я думаю, что мой предыдущий комментарий отвечает хотя бы на часть «почему». Однако, по общему признанию, у меня нет примера «естественных» проблем, которые находятся в AC0 и требуют схем глубины 10 ^ {10 ^ 100}.

Цуёси Ито

Существует множество интересных реальных проблем, которые могут быть решены в постоянном времени и в постоянном пространстве (практически в любой модели вычислений), но теперь у людей есть идея, как их решать на практике. Экстремальными примерами являются вычисления определенных констант; мы могли бы жестко закодировать правильный ответ (например, 0 или 1), но мы пока не знаем ответа.

Юкка Суомела

Юкка: это проблемные случаи. Диофантовы уравнения (как и уравнения Ферма) неразрешимы как класс, даже если отдельные экземпляры, которые мы решили, фактически имеют контуры с постоянной глубиной.

Андрас Саламон

@ András: Если вы предпочитаете решать задачи с бесконечным числом случаев «да» и «нет»: пусть

состоит из всех четных чисел и

, где

если у белого игрока есть выигрышная стратегия в шахматах, а в противном случае

. Тривиально, существует очень простое семейство цепей, которое определяет

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

L

$L$

x

$x$

x = 1

$x = 1$

x = 3

$x = 3$

L

$L$

Юкка Суомела

Ответы:

Если вам нужен пример функции AC ^0, которая требует глубины и не может быть вычислена цепями AC ⁰ глубины , то попробуйте функции Sipser $d$ $d-1$ $S^{d,n}$ $d$ $d-1$

Итак, вычисления $S^{d,n}$ $d = 10^{10^{100}}$

$10^{10^{100}}$

Робин Котари
источник

Это здорово, спасибо! Может быть, вы можете добавить неформальное определение функций Sipser? Я не знал об этом имени.

Микаэль Кадилхак

@ Михаэль: К сожалению, у меня нет хорошего интуитивного определения функций Sipser. Идея состоит в том, чтобы сделать функцию d-квантификаторов такой, чтобы никакая схема глубины d-1 не могла ее вычислить. Поэтому мы хотим, чтобы d-квантификаторы определяли количественно по очень большому количеству переменных. Есть хорошая статья Иддо Цамерета под названием «Разделение цепей постоянной глубины с помощью функций Sipser» ( itcs.tsinghua.edu.cn/~tzameret/SipserSwitching.pdf ), которая формально определяет функции на странице 7.

Робин Котари

Вся эта иерархия намеренно устойчива при полиномиальных изменениях входного размера. Любой класс в нем может, таким образом, содержать функции, сложность которых, скажем, n ^ {1000000000}, которая была бы теоретически "выполнимой", но, конечно, не практически. Это, однако, скорее всего, будет очень искусственными проблемами. В частности, с помощью аргумента подсчета существует семейство формул DNF (= AC ^ 0 глубина 2 цепи) размером n ^ 1000000, которые не может вычислить ни один алгоритм, время выполнения которого меньше, чем n ^ 999999. (В единой обстановке мы ожидаем чего-то подобного, но не можем доказать это.)

Ноам
источник

Проблема остановки, когда вход представлен в унарном виде, находится в AC ^ 0 и все же совершенно неосуществима в реальности. Я не уверен, что это то, что вы имели в виду, но это может быть то, что имел в виду Иммерман.

Elad
источник

Я думаю, классы на диаграмме определены с некоторым понятием единообразия? В противном случае восходящее направление не представляло бы сдерживания, поскольку P не содержит неоднородного AC ^ 0.

Робин Котари

A C^{0}

$AC^0$

{0, 1}

$\{0,1\}$

{0, m a x; X, B I T, \leq, =}

$\{0,max; X,BIT,\le,=\}$

X

$X$

Точка хорошо взята. В качестве альтернативы, следуя Erdos, можно вместо этого предложить проблему, которая для любого входа выводит число Рамси для красной шестерки и синей шестерки.

Elad