Нижняя граница размера формулы для функций AC0

Вопрос:

Какова самая известная нижняя граница размера формулы для явной функции в AC ⁰ ? Существует ли явная функция с нижней границей $\Omega(n^2)$ ?

Задний план:

Как и большинство нижних границ, трудно найти нижние границы размера формулы. Меня интересуют нижние границы размера формулы над стандартным набором универсальных вентилей {AND, OR, NOT}.

Самая известная нижняя граница размера формулы для явной функции над этим набором логических элементов равна $\Omega(n^{3-o(1)})$ для функции, определенной Андреевым. Эта граница была показана Хостадом, улучшив нижнюю оценку Андреева $\Omega(n^{2.5-o(1)})$ . Другой явной нижней границей является нижняя граница Храпченко $\Omega(n^2)$для функции четности.

Однако эти две функции не находятся в AC ⁰ . Мне интересно, если мы знаем явную функцию в AC ⁰ с квадратичной (или лучше) нижней границей. Лучшая оценка, которую я знаю, это нижняя граница $\Omega(n^2/\log n)$ для функции Различия Элементов, как показано Нечипоруком. Обратите внимание, что функция отличимости элемента находится в AC ⁰ , поэтому я ищу нижнюю границу для явной функции AC ^0, которая лучше, чем $\Omega(n^2/\log n)$ , предпочтительно $\Omega(n^2)$ .

Дальнейшее чтение:

Отличный ресурс по этой теме - «Сложность булевых функций: достижения и границы» Стасиса Юкны. Черновик книги доступен бесплатно на его сайте.

Хороший вопрос! Храпченко определенно не может дать квадратичные нижние оценки для функций . Его нижняя граница фактически равна как минимум квадрату средней чувствительности. И все функции в A C 0 имеют полулогарифмическую среднюю чувствительность. Субботовская-Андреев, по-видимому, также не может дать такую ​​функцию, потому что аргумент, который они используют (случайное ограничение приводит к гораздо меньшим формулам), как раз и является причиной принудительного увеличения размера схемы A C 0 ; Переключающая лемма Хастада (не совсем уверен, просто интуиция). Единственная надежда - Нечипорук. Но его аргумент не может дать больше n 2 / log $AC^0$$AC^0$$AC^0$$n^2/\log n$По информационным теоретическим причинам. Так может ли быть так, что все в имеет формулы квадратичного (или даже меньшего) размера? Я не верю в это, но не смог быстро найти контрпример. $AC^0$

На самом деле, феномен Аллендера-Куки возникает и в другом контексте - в сложности графа. Скажем , что схема переменных представляет собой двудольный п × п граф G на вершинах V = { 1 , ... , 2 п } , если для каждого входного вектора а с ровно два 1s, скажем, позиции я и J ( я ≤ п , J > п ) схема принимает тогда и только тогда вершины я и $2n$$n\times n$$G$$V=\{1,\ldots,2n\}$$a$$i$$j$$i\leq n$$j>n$$a$$i$$j$смежны в . Проблема: проявляет явный граф G требует , по крайней мере п х ворот , чтобы быть представлена монотонной Σ 3 -circuit. Похоже , невинный вопрос (так как большинство графов требуют около п +1 / +2 ворот. Но любой такого граф даст нам булеву функцию 2 м = 2 лога п переменных , требующие немонотонную логарифмическую глубину схему суперлинейного размера (по результатам Доблестный). Таким образом, даже доказательство n ϵ нижних границ для схем глубины 3 может быть проблемой. $G$$G$$n^{\epsilon}$ $\Sigma_3$$n^{1/2}$$2m=2\log n$$n^{\epsilon}$

Спасибо, Каве, за желание взглянуть на главы о сложности доказательства!

Относительно вопроса Робина, во-первых, примечание содержит функции, требующие формул (и даже цепей) размера n k для любой константы k . Это следует, скажем, из простого факта, что A C 0 содержит все DNF с постоянно длинными мономами. Таким образом, A C 0 содержит не менее exp ( n k ) различных функций для любого k . С другой стороны, мы имеем не более функций exp ( t log n ), вычисляемых по формулам размера $AC^0$ $n^k$$k$$AC^0$$AC^0$$\exp(n^k)$$k$$\exp(t\log n)$$t$,

Я коротко обсудил вопрос получения явных нижних границ или больше с Игорем Сергеевым (из Московского университета). Одной из возможностей может быть использование метода Андреева, но применение к некоторой другой, более простой для вычисления функции вместо контроля четности. То есть рассмотрим функцию из n переменных вида F ( X ) = f ( g ( X 1 ) , … , g ( X b ) ), где b = log n, а g - функция из $n^2$$n$$F(X)=f(g(X_1),\ldots,g(X_b))$$b=\log n$$g$ из n / b переменных; f - одна из самых сложных функцийпеременных b (достаточно просто наличия f ). Нам нужно только, чтобы функцию g нельзя было «убить» в следующем смысле: если мы фиксируем всепеременные,кроме k, в X , то должна быть возможность исправить все, кроме одной из оставшихся переменных в g, чтобы полученная подфункция g это одна переменная. Тогдаприменяя аргумент Андреева и используя результат Hastad о томчто сжатие постоянная,крайней мере 2 (не только 3 /$AC^0$$n/b$$f$$b$$f$$g$$k$$X$$g$$g$$2$$3/2$как ранее показала Сибботовская), полученная нижняя оценка для будет около n 3 / k 2 . Конечно, мы знаем, что любую функцию в A C 0 можно убить, зафиксировав все переменные, кроме n 1 / d , для некоторой константы d ≥ 2 . Но , чтобы получить п 2 нижняя граница этого будет достаточно , чтобы найти явную функцию A C 0 , которые не могут быть убиты, фиксируя все , но, скажем, п 1 /$F(X)$$n^3/k^2$$AC^0$ $n^{1/d}$$d\geq 2$$n^2$$AC^0$$n^{1/2}$переменные. Нужно искать такую ​​функцию на глубине больше двух.

На самом деле, для функции как указано выше, можно получить нижние оценки для n 2 / log n с помощью простого жадного аргумента, без Нечипорука, без Субботовской и без случайных ограничений! Для этого достаточно просто, чтобы «внутренняя функция» g (Y) была нетривиальной (зависит от всех ее n / b переменных). Более того, оценка верна для любого базиса постоянных вееров, а не только для формул де Моргана.$F(X)$$n^2/\log n$$n/b$

Доказательство: учитывая формулу для с s листами, выберите в каждом блоке X i переменную, которая наименьшее число раз появляется в виде листа. Затем установите все остальные переменные в соответствующие константы так, чтобы каждый g ( X i ) превращался в переменную или ее отрицание. Полученная формула будет тогда как минимум в n / b раз меньше, чем исходная формула. Таким образом, s не менее n / b = n / log $F(X)$$s$$X_i$$g(X_i)$$n/b$$s$$n/b=n/\log n$умножить на формулу размера от f , то есть s ≥ n 2 - o ( 1 ) . QED$2^b/\log b=n/\log\log n$$f$$s\geq n^{2-o(1)}$

Для того, чтобы получить или более, один должно включать Субботовский-Hastad эффект усадки при случайных ограничениях. Возможным кандидатом может быть какая-то версия функции Сипсера, используемая Hastad, чтобы показать, что схемы глубины ( d + 1 ) более мощные, чем схемы глубины d .$n^2$$(d+1)$$d$