Обведите нижние границы над произвольными наборами вентилей

40

В 1980-х годах Разборов, как известно, показал, что существуют явные монотонные булевы функции (такие как функция CLIQUE), которые требуют экспоненциально большого количества вентилей AND и OR для вычисления. Однако базис {AND, OR} над булевой областью {0,1} является лишь одним примером интересного набора элементов, который не может быть универсальным. Это приводит к моему вопросу:

Существует ли какой-либо другой набор вентилей, интересно отличающийся от монотонных вентилей, для которых известны экспоненциальные нижние границы размера схемы (без глубины или других ограничений на схему)? Если нет, то существует ли какой-либо другой набор элементов, который является вероятным кандидатом для таких нижних границ - границ, которые не обязательно требуют прорыва через барьер Natural Proofs, как это было в результате монотонных схем Разборова?

Если такой набор затворов существует, то, конечно, он будет выше k-арного алфавита для k≥3. Причина в том, что в двоичном алфавите

(1) монотонные ворота ({И, ИЛИ}),

(2) линейные ворота ({NOT, XOR}) и

(3) универсальные ворота ({И, ИЛИ, НЕ})

в основном исчерпывают интересные возможности, как следует из теоремы Поста о классификации. (Обратите внимание, что я предполагаю, что константы --- 0 и 1 в двоичном случае --- всегда доступны бесплатно.) С линейными вентилями каждая булева функция f: {0,1} n → {0,1} это вычислимый вообще вычислим по схеме линейного размера; с универсальным набором, конечно, мы столкнулись с естественными доказательствами и другими ужасающими барьерами.

С другой стороны, если мы рассмотрим наборы ворот для алфавита из 3 или 4 символов (например), то откроется более широкий набор возможностей - и, по крайней мере, насколько мне известно, эти возможности никогда не были полностью намечены с точки зрения теории сложности (поправьте меня, если я ошибаюсь). Я знаю, что возможные множества ворот широко изучаются под названием «клоны» в универсальной алгебре; Хотелось бы, чтобы я был более знаком с этой литературой, чтобы я знал, что, если что-нибудь, результаты из этой области значат для сложности схемы.

В любом случае, не может быть и речи о том, что есть другие нижние границы драматического контура, готовые к испытанию, если мы просто расширим класс наборов гейтов по конечным алфавитам, которые мы готовы рассмотреть. Если я не прав, скажите, пожалуйста, почему!

Скотт Ааронсон
источник
3
Если вы рассматриваете функции , то ситуация более сложна для линейных вентилей, потому что аргумент подсчета показывает, что есть функции, которые требуют Ω ( n 2f:{0,1}n{0,1}nлогические элементы для вычисления, хотя, насколько я знаю, нет явных примеров функций, которые требуют схем суперлинейного размера. Ω(n2log(n))
Григорий Ярославцев
2
Только примечание: если вы заменяете монотонные логические элементы на элементы, которые вычисляют любые неубывающие действительные функции , вы также получаете экспоненциальные нижние границы для размера цепей. Это было доказано Пудлаком: нижние оценки для разрешений и разрезания плоскостей, доказательства и монотонные вычисления , J. of Symb. Logic 62 (3), 1997, pp.981-998.
Иддо Цамерет
2
Григорий: спасибо; Я обсуждал, стоит ли упоминать это в ОП! Вы правы в том, что у нас нет явной суперлинейной нижней границы на число вентилей XOR, необходимых для вычисления линейной функции f: {0,1} <sup> n </ sup> & rarr; {0,1} < SUP> п </ SUP>. С другой стороны, нетрудно найти кандидатов для линейных преобразований, которые <i> должны </ i> требовать & Omega; (n log n) вентилей XOR (преобразование Фурье, матрица "набивки Серпинского" ...) , и Брэм Коэн предложил пример функции, которая должна требовать & Omega (n <sup> 3/2 </ sup>) ворот XOR (я не помню этого, но мог бы спросить его).
Скотт Ааронсон
Даже для размера 3 алфавита решетка клонов неисчислима и содержит каждую конечную решетку в качестве подрешетки. Таким образом, существует бесконечно много, возможно, интересных оснований для операций. Я не знаю какой-либо работы по использованию небулевых клонов для нижних границ цепей, но это, кажется, стоит исследовать более подробно.
Андрас Саламон
3
Скотт, ты знаешь подходящий аналог для класса AC ^ 0 для больших афабетов? Позвольте мне также отметить, что можно рассмотреть понятия монотонности для больших алфавитов (Эльчанан Моссель и я написали о резких порогах для этих front.math.ucdavis.edu/1011.3566 ), так что, возможно, теорема Расборова распространяется на монотонные контуры над большим алфавитом для определенного понятия монотонность.
Гил Калай

Ответы:

25

(Удалено из комментариев, как предложил Суреш. Обратите внимание, что некоторые ошибки в комментарии исправлены здесь.)

Спасибо Скотту за отличный вопрос.

Скотт, кажется, предполагает, что причиной сложности нижних границ может быть ограниченный язык операций в булевом случае. Счетный аргумент Шеннона, который показывает, что большинство цепей должно быть большим, основан на разрыве между счетной выразительной силой и бесчисленным количеством цепей. Этот пробел исчезает, когда в алфавите есть как минимум 3 символа.

Для размера алфавита 2 (логический случай) решетка клонов счетно бесконечна и называется решеткой Поста .

Изображение решетки поста из Википедии

Решетка Поста также поясняет, почему для булева случая есть только несколько интересных базисов операций.

Для размера алфавита 3 или более решетка клонов неисчислима. Кроме того, решетка не удовлетворяет какой-либо нетривиальной идентичности решетки, поэтому представляется невозможным дать полное описание решетки. Для размера алфавита 4 или более решетка клонов фактически содержит каждую конечную решетку в качестве подрешетки. Таким образом, существует бесконечно много, возможно, интересных основ операций, которые нужно учитывать, когда в алфавите 3 или более символов.

  • Булатов, Андрей А., Условия, удовлетворяемые решетками клонов , Algebra Universalis 46 237–241, 2001. doi: 10.1007 / PL00000340

Скотт спросил далее: остается ли решетка клонов несчетной, если предположить, что константы доступны бесплатно?

Ответ таков: посмотрите, например,

  • Градимир Войводич, Йованка Пантович и Ратко Тошич . Число клонов, содержащих унарную функцию , NSJOM 27 83–87, 1997. ( PDF )
  • Й. Пантович, Р. Тошич и Г. Войводич, Мощность функционально полных алгебр на трехэлементном множестве , Algebra Universalis 38 136–140, 1997. doi: 10.1007 / s000120050042

хотя, видимо, это было опубликовано ранее:

  • Агостон И., Деметрович Дж. И Ханнак Л. О числе клонов, содержащих все константы , Сб. Математика Soc. Янош Боляй 43 21–25, 1983.

Хорошее конкретное утверждение от:

  • А. Булатов, А. Крохин, К. Сафин, Е. Суханов, О структуре решеток клонов , В кн . : «Общая алгебра и дискретная математика», редакторы: К. Денеке и О. Людерс, 27–34. Хельдерман Верлаг, Берлин, 1995. ( PS )

k3Lk20

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

Дополнительные связи между теорией клонов и информатикой, вероятно, также будут представлять большой интерес для математиков, работающих в универсальной алгебре. Предыдущий пример такого рода взаимодействия появился, когда Питер Дживонс показал, что алгебры могут быть связаны с языками ограничений таким способом, который позволяет преобразовывать результаты отслеживаемости в свойства алгебры. Андрей Булатов использовал это, чтобы доказать дихотомию для CSP с размером домена 3. С другой стороны, в результате применения компьютерных наук наблюдается оживление интереса к теории ручного сравнения. Интересно, что следует из связи между теорией клонов и сложностью небулевой схемы.

Андраш Саламон
источник
Большое спасибо, Андраш! Я проверю работу Агостона и соавторов. когда я получу шанс. В то же время я просмотрел список максимальных преждевременных клонов на наборе из 3 элементов из Pantović et al. бумага, на которую вы ссылались, и я не думаю, что кто-либо из них является кандидатом на «новые» схемы нижних границ. (Для некоторых из них экспоненциальные нижние границы непосредственно следуют из монотонной нижней границы Разборова; для других нам понадобятся нижние границы для общих схем или для линейных схем.) Но даже в случае k = 3 клоны меньше, чем предварительные кажется, стоит посмотреть.
Скотт Ааронсон
15

Это убрано из комментариев, как предложил Суреш.

f:0,1n0,1nΩ(n2log(n))

n2log(n)cc

Ω(nlogn)Ω(n3/2)

Редактировать 2. Основным препятствием является то, что у нас нет никаких методов для доказательства нелинейных нижних границ, даже для линейных ворот, насколько я знаю (для линейных нижних границ можно использовать исключение ворот, что очень маловероятно, чтобы -линейные границы). Хотя, похоже, некоторые методы из линейной алгебры действительно должны быть полезны. Поэтому подходить к кандидатам приятно, но в любом случае нужны новые методы.

Григорий Ярославцев
источник
11
  1. {0,1}aZ3n={0,1,2}nmin(x,y)xymod2f(a)=0a02a12n/nf

  2. 2y=AxGF(2)nlog3/2nn1+cc>02

Стасис
источник
2
Уважаемый Стасис, могу я предложить вам зарегистрировать свой аккаунт? Это позволит вам использовать ту же учетную запись пользователя, чтобы публиковать ответы и редактировать их позже, среди прочего. (Дайте мне знать, если вы решите зарегистрироваться, и я объединю ваши предыдущие учетные записи с ним, чтобы вы также могли редактировать свои предыдущие сообщения.)
Kaveh
1
Kxi=aanKΩ(nK)
Стасис