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

17

Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине, полиномиальному размеру, неограниченному разветвлению AND, OR, NOT и модулю gates, где . Однако получение конкретных нижних оценок для полилогарифмических контуров глубины, кажется, недостижимо при использовании классических методов, таких как ограничение входных данных и аппроксимация полиномов на конечных полях.AC0pAC0[q]AC0[q]qgcd(p,q)=1

Я знаю статью STOC'96, которая приводит к теории геометрической сложности и которая показывает, что эффективные параллельные вычисления, использующие операции без побитовых операций, не могут вычислить проблему минимальных затрат.

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

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

Во-вторых, насколько полезно следующее утверждение для теоретического сообщества?

Размер схемы NC , вычисляющей булеву функцию f:{0,1}n{0,1} составляет не менее l , где l - некоторая математическая величина, зависящая от твердости целевая функция f . Значение l может быть, например, комбинаторной величиной, такой как расхождение, линейной алгебраической величиной, такой как ранг матрицы определенного типа над полем, или некоторой совершенно новой величиной, которая ранее не использовалась в теории сложности.

шень
источник
6
Слово предостережения в порядке: даже логарифмическая глубина, если она еще не понята. У нас еще нет суперлинейной (!) Нижней границы для NC ^ 1-цепей. Здесь жесткость матрицы является желаемой «комбинаторной величиной», но нам не хватает достаточно сильных нижних границ для этой величины. Еще более удручающе то, что сверхлинейная нижняя граница не известна для NC ^ 1-цепей, вычисляющих линейное преобразование f (x) = Ax над GF (2), даже если в качестве логических элементов допускаются только XOR для fanin-2. (Тогда почти для всех матриц A требуется n ^ 2 / \ log n вентилей любой глубины.)
Stasys
@Stasys, я думаю, твой комментарий может быть ответом.
Каве

Ответы:

16

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

Согласно другому ограничению, которое является монотонным ограничением для монотонных булевых функций, в моей совместной работе с Аароном Потечиным ( ECCC и STOC ) используется фурье-аналитический (или перечислительный-комбинаторный) подход для доказательства монотонных нижних границ глубины контура . Это улучшает ранний результат Ран Раза и Пьера Маккензи, который расширяет рамки коммуникационной игры Маурисио Карчмера и Ави Вигдерсона относительно глубины контура.

Скотт Ааронсон и Ави Вигдерсон предложили еще одну линию исследований для расширения игры Карчмера – Вигдерсона в качестве упомянутой коммуникационной игры , чье расширение к протоколу конкурирующего доказателя предлагается в качестве подхода к отделению NC от P Гиллатом Колом и Ран Разом ( ECCC и ITCS ).

Помимо изучения синтаксического ограничения монотонности, есть подход к изучению семантического ограничения, относящегося к играм в гальку (называемые экономными программами ветвления), выполненный Стивеном Куком, Пьером МакКензи, Дастином Вером, Марком Браверманом и Рахул Сантанам. Под строгим ограничением Дастина Вера существует сильная нижняя граница , совпадающая с наиболее известной верхней границей для P-полных задач. Эти результаты касаются детерминированной сложности пространства, которая ограничивает параллельное время или глубину контура известными результатами моделирования (например, начиная с ).AlternatingTime[t]DeterministicSpace[t]

Что касается вопроса, касающегося размера и глубины цепей, может быть связан следующий подход. Ричард Липтон и Райан Уильямс показывают, что, учитывая достаточно сильную нижнюю границу по глубине (то есть ), слабая нижняя граница по размеру (т.е. n 1 + Ω ( 1 ) ) может отделить NC от P. Этот результат вытекает из аргумента компромисса между глубиной и размером, основанного на уважении блоков. Более ранний результат о глубине торговли за размер обусловлен Аллендером и Куки, основанными на идее самовосстановления, но он изучал классы меньшей сложности, такие как NC 1 и NL.n1O(1)n1+Ω(1)1

Обратите внимание, что среди вышеупомянутых подходов некоторые из них учитывают как размер, так и глубину контуров, в то время как другие подходы учитывают только глубину контура. В частности, полуалгебро-геометрический подход Малмулей , подход с протоколом конкурирующих доказательств , изученный Кол-Разом , и подход Аллендера-Куки и Липтона-Уильямса, основанный на соотношении размеров и глубины, касаются как размера, так и глубины. схем. Результаты Чана-Потечина , Раз-Мак-Кензи , Кука-Мак-Кензи-Вер-Бравермана-Сантанама и Вера дают нижние границы глубины контура при ограниченных настройках независимо от размера. Также упомянутая коммуникационная играАаронсон-Вигдерсон касается только глубины контура.

Мы все еще согласны с тем, что некоторая P-полная задача не может быть вычислена схемами небольшой глубины (т. ), независимо от размера. Если размер не имеет значения для контуров с малой глубиной (с ограниченным разветвлением), то, возможно, имеет смысл сосредоточиться больше на глубине контура, чем на размере контуров с малой глубиной.logO(1)n

siuman
источник
Благодарность! Насколько вы знаете, утверждение, которое есть в Q2, не всем найдено, не так ли? То есть, в отличие от методов нижней границы сложности связи, у нас нет математической величины, дающей нижние границы схемы ЧПУ?
Шен
@shen, я добавил еще два параграфа в конце. Надеюсь, что это полезно.
siuman
2
Идея о том, что нижние границы слабого размера могут быть усилены, использованная в статье Липтона-Уильямса, на самом деле принадлежит Аллендеру и Куки ( eccc.hpi-web.de/report/2008/038 ).
Эмиль Йержабек поддерживает Монику
@ EmilJeřábek Спасибо! Я добавил эту статью. Надеюсь, что ответ выглядит лучше.
Сьюман
14

Следуя предложению Каве, я помещаю свой комментарий как (расширенный) ответ.

Относительно Q1 , слово предостережения в порядке: даже логарифмическая глубина, если она далека от понимания, не говоря уже о полилогарифмической. Итак, в немонотонном мире реальная проблема гораздо менее амбициозна:

Проблема логарифмической глубины: докажите суперлинейную (!) Нижнюю границу для -цепей. NC1

Проблема остается открытой (на данный момент более 30 лет) даже для линейных -цепей. Это схемы fanin- 2 над базисом { , 1 } , и они вычисляют линейные преобразования f ( x ) = A x над G F ( 2 ) . Простой подсчет показывает, что почти для всех матриц A требуются Ω ( n 2 / log n ) вентилей любой глубины. NC12{,1}f(x)=AxGF(2)AΩ(n2/logn)

Что касается Q2 : Да, у нас есть некоторые алгебраические / комбинаторные меры, нижние границы которых бьют схемы глубины логарифмического ряда. К сожалению, пока мы не можем доказать достаточно большие оценки этих мер. Скажем, линейный - схем, такая мера является жесткость R ( г ) матрицы А . Это наименьшее количество записей в A, которое нужно изменить, чтобы уменьшить ранг до r . Легко показать, что R A ( r ) ( n -NC1 RA(r)AAr выполняется для каждой булевой n × n- матрицы A , и Валиант (1977) показал, что эта граница плотна почти для всех матриц. Для того, чтобы бить лог-глубины цепи, то достаточночтобы показать последовательность булевых п × п матрицтакимчтоRA(r)(nr)2n×nAn×nA

для постоянных ϵ , δ > 0 . RA(ϵn)n1+δϵ,δ>0

Лучшее, что мы знаем на сегодняшний день, это матрицы с R A ( r ) ( n 2 / r ) log ( n / r ) . Для матриц Сильвестра (т.е. внутренние матрицы продукта), нижняя граница Q , ( п 2 / г ) является легко показать . ARA(r)(n2/r)log(n/r)Ω(n2/r)

У нас есть комбинаторные меры для общих (нелинейных) -цепей, а также для двудольного графа n × n G , пусть t ( G ) наименьшее число t, такое, что G можно записать как пересечение двудольного t графы, каждый из которых представляет собой не более t полных двудольных графов. Чтобы превзойти общие схемы логарифмической глубины, было бы достаточно найти последовательность графиков сNC1n×nGt(G)tGtt

для постоянной ϵ > 0t(Gn)nϵϵ>0

(см., например, здесь, как это происходит). Опять же , почти все графы имеют . Тем не менее, лучшим остается нижняя граница t ( G ) log 3 n для матриц Сильвестра из-за Локама . t(G)n1/2t(G)log3n

Наконец, позвольте мне упомянуть, что у нас даже есть «простая» комбинаторная мера (величина) со слабой (линейной) нижней границей, которая дала бы даже экспоненциальные (!) Нижние оценки для немонотонных цепей. Для получения двудольного графа G , пусть с ( G ) наименьшее количество fanin- 2 союза ( ) и пересечения ( ) операции , которые необходимы для получения G при запуске от звезд; звезда - это набор ребер, соединяющих одну вершину со всеми вершинами на другой стороне. Почти все графы имеют c ( G ) = Ω ( n 2n×nGc(G)2G . С другой стороны, нижняя границаc(G)=Ω(n2/logn)

для постоянной ϵ > 0c(Gn)(4+ϵ)nϵ>0

будет означать нижнюю оценку на немонотонную сложность схемы явной булевой функции f G из N переменных. Если G представляет собой граф n × m с m = o ( n ) , то достаточно даже нижней границы c ( G n ) ( 2 + ϵ ) n (опять же, см., Например, здесь, как это происходит). Нижние оценки c ( GΩ(2N/2)fGNGn×mm=o(n)c(Gn)(2+ϵ)n можно показать для относительно простых графиков. Проблема, однако, заключается в том, чтобы сделать это с " - ϵ ", замененным на " + ϵ ". Более комбинаторные меры сложности нижних границ схемы (включая схемы A C C ) можно найти в книге. c(G)(2ϵ)nϵ+ϵACC

PS Итак, мы с постоянным множителем показываем P N P ? Конечно, нет. Я упомянул эту последнюю меру c ( G ) только для того, чтобы показать, что следует относиться к «усилению» (или «увеличению») нижних границ со здоровой частью скептицизма: даже если границы, которые нам нужны, выглядят «невинно», они намного меньше ( линейный), чем требуется почти всем графам (квадратичным), сложность доказательства (слабой) нижней границы может быть даже больше. Конечно, найдя комбинаторную меру, мы можем кое- что сказать о том, какие свойства функций делают их вычислительно сложными. Это может быть полезно для доказательства косвенного2+ϵPNPc(G)нижняя граница: некоторый класс сложности содержит функцию, требующую больших схем или формул. Но конечная цель состоит в том, чтобы придумать явную сложную функцию, определение которой не имеет «алгоритмического запаха», не имеет скрытых аспектов сложности.

Стасис
источник
2
Я нахожу это очень интересным: 1. суперлинейная нижняя оценка для линейных функций над представляется очень конкретным нижним вопросом. 2. Нижние границы математических понятий, не связанные напрямую с вычислениями, связаны с нижним пределом схемы. GF(2)
Каве
Ω(f(n))Ω(f(n,r))Ω(f(n,r))nΩ(f(n))
RA(r) r0RA(n)=0