Является ли

23

В опросе Д. Бера, Ф. Грина и С. Гомера «Квантовые схемы малой глубины» (стр. 36 ACM SIGACT News, июнь 2007 г., том 38, № 2) я прочитал следующее предложение:

Классическая версия (в которой вентили и имеют самое большее постоянное разветвление), очевидно, слабее, чем .QAC0ANDORAC0

Ссылка на это требование отсутствует. Я назову этот класс , где означает «ограниченное разветвление». (Зоопарк Сложности закрыт, и я не могу проверить, есть ли такой класс в литературе). Если мы предположим неограниченное разветвление для входных битов, то эти схемы кажутся эквивалентными формулам с постоянной глубиной вплоть до полиномиального увеличения размера, поэтому приведенное выше утверждение не имеет смысла. Вместо этого, если мы предполагаем ограниченный разветвление для входных битов, то я не могу думать ни о каком языке, который отделяет этот класс от . Возможным кандидатом может быть язык , т. е. язык строк только с одним. Это легко показатьACbf0bfAC0X:={x|weight(x)=1}XAC0 , но мне не удалось доказать, что .XACbf0

Вопросы:

Действительно ли слабее, чем ? Если да, то есть какая-нибудь идея или какая-либо ссылка на то, как это доказать? И что это за язык, который разделяет эти два класса? А как насчет ?ACbf0AC0X

Алессандро Косентино
источник
6
Ограничение разветвления входных битов сделает схему линейного размера. Любая функция которая требует суперлинейного размера, будет разделять их. AC0
Каве
2
@Kaveh: Может быть , вы могли бы перепечатывать , что в качестве ответа, возможно с примером явной функции , которая требует супер-линейного размера C 0 схем и может быть, ссылка , которая показывает размер нижней границы? (Или включите аргумент в свой ответ, если он очень прост?)AC0
Робин Котари
2
@Kaveh Спасибо. Я не знал, что разделение между и линейными контурами постоянной глубины (по-видимому, называется L C 0 ) было известно. Ссылка "Детерминированные ограничения в сложности схем" С. Чаудхури и Дж. Радхакришнана. @Kaveh Можете ли вы сделать свой комментарий ответом? AC0LC0
Алессандро Косентино
2
Как обсуждалось в последующем вопросе cstheory.stackexchange.com/questions/7447/… , - это то же самое, что и формула линейного размера. ACbf0
Domotorp

Ответы:

23

Ограничение разветвления входных битов и вентилей сделает размер схемы линейным. Пусть будет границей разветвления ворот и входов. Это DAG с максимальной степенью выхода, ограниченной k, и максимальной длиной пути d . Количество доступных проводов на каждом уровне можно увеличить K раз, и количество доступных проводов на вершине к п , так что общее количество проводов в цепи не превосходит к п Е д я = 0 K яK d + 1 n, который является O ( n ) .kkdkknkni=0dkikd+1nO(n)

Любая функция которая требует суперлинейного размера, будет отделять класс функций с ограниченным разветвлением (также применяется к входным битам) от A C 0 . Вот некоторые примеры:AC0AC0

  1. [CR96]: функция которой требуется суперлинейный размер, равна 1AC0 приблизительный селектор14. А -приближенный селектор - это любая функция, значение которой равно:14

    • всякий раз, когда число 1 с не более n01 ,n4
    • всякий раз, когда число 0 с не более n10 ,n4
    • в противном случае может быть или 1 .01
  2. [Ros08] показывает, что клик имеет сложность функций A C 0 n Θ ( k ) ( n 2 входных битов являются возможными ребрами графа с n вершинами). Это дает нижний предел размера суперлинии при k > 2 .kAC0nΘ(k)n2nk>2

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

    • существование пути длины 2 в данном графе,
    • ,#1(x)=2

    поскольку они требуют суперконстантного числа вентилей в зависимости от бита, что невозможно в .ACbf0

  4. Самым простым примером является шлюз дубликатора, то есть шлюз, который создает копии своего входного бита. Это невозможно в A C 0 b f, поскольку только O ( 1 ) вентилей может зависеть от каждого входного бита.ω(1)ACbf0O(1)

Также любая схема размера S может быть превращена в формулу размера не более k d S и, следовательно, имеет формулу A C 0 b f размера k 2 d + 1 n, поэтому любая функция суперлинейного A C 0 Сложность формулы не будет в A C 0 b f .ACbf0SkdSACbf0k2d+1nAC0ACbf0


Ссылки:

[CR96] С. Чаудхури и Дж. Радхакришнан, « Детерминированные ограничения в сложности схем », 1996

[Ros08] Бенджамин Россман, " О постоянной глубине сложности k-Clique ", 2008

[Juk] Стасис Юкна, « Сложность булевой функции: достижения и границы », черновик

Кава
источник
12
Более недавнее разделение между и A C 0 следует из этого результата благодаря Бенджамину Россману. Он показывает, что для всей константы k (также некоторого растущего k ) и константы d любая схема глубины d для k -клика на графе n вершин должна иметь размер Ω ( n k / 4 ) . Это означает , что иерархия языков принята A C 0 схемы размера п к (для различных кLC0AC0kkddknΩ(nk/4)AC0nkk) на самом деле бесконечен.
Srikanth
1
Я обновил ответ, благодаря Алессандро, Домоторпу, Робину, Сриканту и Стасису.
Каве
1
@Kaveh: Хорошо, спасибо. Если вы найдете способ изменить результат Россмана, мне будет интересно услышать его. Что касается функции порога-2, я думаю, что мы можем показать, что она не в этом классе, отметив, что все функции в этом классе имеют формулы линейного размера, а порог-2 имеет нижнюю границу размера формулы . Ω(nlogn)
Робин Котари
1
@Kaveh: Если под вы подразумеваете путь длины k , вам следует иметь в виду, что для этих функций существуют схемы A C 0 размером 2 k n O ( 1 ) (это в основном вытекает из метода цветового кодирования Алон, Юстер и Цвик). Я не уверен, что техника Россмана дает такие ограничения (хотя я не знаю ни одной причины, почему это не должно). PkkAC02knO(1)
Srikanth
1
AC0