Сложность схемы с ограниченной глубиной является одной из основных областей исследования в теории сложности схемы. Эта тема имеет происхождение в результатах типа «функция четности не в » и « функция mod не вычисляется », где - класс языков, разрешимых по неоднородности, постоянной глубине, полиномиальному размеру, неограниченному разветвлению AND, OR, NOT и модулю gates, где . Однако получение конкретных нижних оценок для полилогарифмических контуров глубины, кажется, недостижимо при использовании классических методов, таких как ограничение входных данных и аппроксимация полиномов на конечных полях.
Я знаю статью STOC'96, которая приводит к теории геометрической сложности и которая показывает, что эффективные параллельные вычисления, использующие операции без побитовых операций, не могут вычислить проблему минимальных затрат.
Это означает, что в некоторых ограниченных настройках мы можем доказать нижние оценки для некоторой полной задачи.
Во-первых, существуют ли другие методы или методики, которые могут быть правдоподобными для доказательства нижних границ полилогарифмического контура глубины?
Во-вторых, насколько полезно следующее утверждение для теоретического сообщества?
Размер схемы , вычисляющей булеву функцию составляет не менее , где - некоторая математическая величина, зависящая от твердости целевая функция . Значение может быть, например, комбинаторной величиной, такой как расхождение, линейной алгебраической величиной, такой как ранг матрицы определенного типа над полем, или некоторой совершенно новой величиной, которая ранее не использовалась в теории сложности.
Ответы:
Что касается методов проверки нижних границ глубины полихарифной схемы, все существующие подходы работают в ограниченных условиях. Например, в упомянутой вами работе, ведущей к GCT , нижняя граница применяется к модели ограниченного PRAM без битовых операций.
Согласно другому ограничению, которое является монотонным ограничением для монотонных булевых функций, в моей совместной работе с Аароном Потечиным ( ECCC и STOC ) используется фурье-аналитический (или перечислительный-комбинаторный) подход для доказательства монотонных нижних границ глубины контура . Это улучшает ранний результат Ран Раза и Пьера Маккензи, который расширяет рамки коммуникационной игры Маурисио Карчмера и Ави Вигдерсона относительно глубины контура.
Скотт Ааронсон и Ави Вигдерсон предложили еще одну линию исследований для расширения игры Карчмера – Вигдерсона в качестве упомянутой коммуникационной игры , чье расширение к протоколу конкурирующего доказателя предлагается в качестве подхода к отделению NC от P Гиллатом Колом и Ран Разом ( ECCC и ITCS ).
Помимо изучения синтаксического ограничения монотонности, есть подход к изучению семантического ограничения, относящегося к играм в гальку (называемые экономными программами ветвления), выполненный Стивеном Куком, Пьером МакКензи, Дастином Вером, Марком Браверманом и Рахул Сантанам. Под строгим ограничением Дастина Вера существует сильная нижняя граница , совпадающая с наиболее известной верхней границей для P-полных задач. Эти результаты касаются детерминированной сложности пространства, которая ограничивает параллельное время или глубину контура известными результатами моделирования (например, начиная с ).AlternatingTime[t]⊆DeterministicSpace[t]
Что касается вопроса, касающегося размера и глубины цепей, может быть связан следующий подход. Ричард Липтон и Райан Уильямс показывают, что, учитывая достаточно сильную нижнюю границу по глубине (то есть ), слабая нижняя граница по размеру (т.е. n 1 + Ω ( 1 ) ) может отделить NC от P. Этот результат вытекает из аргумента компромисса между глубиной и размером, основанного на уважении блоков. Более ранний результат о глубине торговли за размер обусловлен Аллендером и Куки, основанными на идее самовосстановления, но он изучал классы меньшей сложности, такие как NC 1 и NL.n1−O(1) n1+Ω(1) 1
Обратите внимание, что среди вышеупомянутых подходов некоторые из них учитывают как размер, так и глубину контуров, в то время как другие подходы учитывают только глубину контура. В частности, полуалгебро-геометрический подход Малмулей , подход с протоколом конкурирующих доказательств , изученный Кол-Разом , и подход Аллендера-Куки и Липтона-Уильямса, основанный на соотношении размеров и глубины, касаются как размера, так и глубины. схем. Результаты Чана-Потечина , Раз-Мак-Кензи , Кука-Мак-Кензи-Вер-Бравермана-Сантанама и Вера дают нижние границы глубины контура при ограниченных настройках независимо от размера. Также упомянутая коммуникационная играАаронсон-Вигдерсон касается только глубины контура.
Мы все еще согласны с тем, что некоторая P-полная задача не может быть вычислена схемами небольшой глубины (т. ), независимо от размера. Если размер не имеет значения для контуров с малой глубиной (с ограниченным разветвлением), то, возможно, имеет смысл сосредоточиться больше на глубине контура, чем на размере контуров с малой глубиной.logO(1)n
источник
Следуя предложению Каве, я помещаю свой комментарий как (расширенный) ответ.
ОтносительноQ1 , слово предостережения в порядке: даже логарифмическая глубина, если она далека от понимания, не говоря уже о полилогарифмической. Итак, в немонотонном мире реальная проблема гораздо менее амбициозна:
Проблема остается открытой (на данный момент более 30 лет) даже для линейных -цепей. Это схемы fanin- 2 над базисом { ⊕ , 1 } , и они вычисляют линейные преобразования f ( x ) = A x над G F ( 2 ) . Простой подсчет показывает, что почти для всех матриц A требуются Ω ( n 2 / log n ) вентилей любой глубины.NC1 2 {⊕,1} f(x)=Ax GF(2) A Ω(n2/logn)
Что касаетсяQ2 : Да, у нас есть
некоторые алгебраические / комбинаторные меры, нижние границы которых бьют схемы глубины логарифмического ряда. К сожалению, пока мы не можем доказать достаточно большие оценки этих мер. Скажем, линейный - схем, такая мера является жесткость R ( г ) матрицы А . Это наименьшее количество записей в A, которое нужно изменить, чтобы уменьшить ранг до r . Легко показать, что R A ( r ) ≤ ( n -NC1 RA(r) A A r выполняется для каждой булевой n × n- матрицы A , и Валиант (1977) показал, что эта граница плотна почти для всех матриц. Для того, чтобы бить лог-глубины цепи, то достаточночтобы показать последовательность булевых п × п матрицтакимчтоRA(r)≤(n−r)2 n×n A n×n A
Лучшее, что мы знаем на сегодняшний день, это матрицы с R A ( r ) ≥ ( n 2 / r ) log ( n / r ) . Для матриц Сильвестра (т.е. внутренние матрицы продукта), нижняя граница Q , ( п 2 / г ) является легко показать .A RA(r)≥(n2/r)log(n/r) Ω(n2/r)
У нас есть комбинаторные меры для общих (нелинейных) -цепей, а также для двудольного графа n × n G , пусть t ( G ) наименьшее число t, такое, что G можно записать как пересечение двудольного t графы, каждый из которых представляет собой не более t полных двудольных графов. Чтобы превзойти общие схемы логарифмической глубины, было бы достаточно найти последовательность графиков сNC1 n×n G t(G) t G t t
(см., например, здесь, как это происходит). Опять же , почти все графы имеют . Тем не менее, лучшим остается нижняя граница t ( G ) ≥ log 3 n для матриц Сильвестра из-за Локама .t(G)≥n1/2 t(G)≥log3n
Наконец, позвольте мне упомянуть, что у нас даже есть «простая» комбинаторная мера (величина) со слабой (линейной) нижней границей, которая дала бы даже экспоненциальные (!) Нижние оценки для немонотонных цепей. Для получения двудольного графа G , пусть с ( G ) наименьшее количество fanin- 2 союза ( ∪ ) и пересечения ( ∩ ) операции , которые необходимы для получения G при запуске от звезд; звезда - это набор ребер, соединяющих одну вершину со всеми вершинами на другой стороне. Почти все графы имеют c ( G ) = Ω ( n 2n×n G c(G) 2 ∪ ∩ G . С другой стороны, нижняя границаc(G)=Ω(n2/logn)
будет означать нижнюю оценку на немонотонную сложность схемы явной булевой функции f G из N переменных. Если G представляет собой граф n × m с m = o ( n ) , то достаточно даже нижней границы c ( G n ) ≥ ( 2 + ϵ ) n (опять же, см., Например, здесь, как это происходит). Нижние оценки c ( GΩ(2N/2) fG N G n×m m=o(n) c(Gn)≥(2+ϵ)n можно показать для относительно простых графиков. Проблема, однако, заключается в том, чтобы сделать это с " - ϵ ", замененным на " + ϵ ". Более комбинаторные меры сложности нижних границ схемы (включая схемы A C C ) можно найти в
книге.
c(G)≥(2−ϵ)n −ϵ +ϵ ACC
PS Итак, мы с постоянным множителем показываем P ≠ N P ? Конечно, нет. Я упомянул эту последнюю меру c ( G ) только для того, чтобы показать, что следует относиться к «усилению» (или «увеличению») нижних границ со здоровой частью скептицизма: даже если границы, которые нам нужны, выглядят «невинно», они намного меньше ( линейный), чем требуется почти всем графам (квадратичным), сложность доказательства (слабой) нижней границы может быть даже больше. Конечно, найдя комбинаторную меру, мы можем кое- что сказать о том, какие свойства функций делают их вычислительно сложными. Это может быть полезно для доказательства косвенного2+ϵ P≠NP c(G) нижняя граница: некоторый класс сложности содержит функцию, требующую больших схем или формул. Но конечная цель состоит в том, чтобы придумать явную сложную функцию, определение которой не имеет «алгоритмического запаха», не имеет скрытых аспектов сложности.
источник