Приблизительная степень

24

РЕДАКТИРОВАТЬ (v2): в конце добавлен раздел о том, что я знаю о проблеме.

РЕДАКТИРОВАТЬ (v3): Добавлено обсуждение пороговой степени в конце.

Вопрос

Этот вопрос в основном справочный запрос. Я не знаю много о проблеме. Я хочу знать, была ли предыдущая работа по этой проблеме, и если да, может ли кто-нибудь указать мне какие-либо статьи, в которых говорится об этой проблеме? Я также хотел бы знать текущие лучшие оценки приблизительной степени . Любая другая информация также будет оценена (например, историческая информация, мотивация, отношение к другим проблемам и т. Д.).AC0

Определения

Пусть - булева функция. Пусть - многочлен от переменных до с действительными коэффициентами. Степень многочлена является максимальной степенью по всем мономам. Степень монома - это сумма показателей различных которые появляются в этом мономе. Например, .p x 1 x n x i deg ( x 7 1 x 2 3 ) = 9f:{0,1}n{0,1}px1xnxideg(x17x32)=9

Многочлен называется \ epsilon -приближенным f, если | f (x) -p (x) | <\ epsilon для всех x . \ Эпсилон -approximate степень булевой функции F , обозначается как \ widetilde {\ textrm {град}} _ {\ эпсилон} (е) , минимальная степень многочлена , что \ эпсилон -approximates е . Для набора функций F , \ widetilde {\ textrm {deg}} _ {\ epsilon} (F) - это минимальная степень d такая, что каждая функция в F может быть \ epsilon -присоединена полиномом степени не более dϵ f | f ( x ) - p ( x ) | < ϵpϵf|f(x)p(x)|<ϵϵ f ~ deg ϵ ( f ) ϵ f F ~ deg ϵ ( F ) d Fxϵfdeg~ϵ(f)ϵfFdeg~ϵ(F)dFдϵd,

Обратите внимание, что каждая функция может быть представлена ​​без ошибок полиномом степени n . Некоторые функции действительно нуждаются в полиноме степени n чтобы приблизиться к любой постоянной ошибке. Паритет является примером такой функции.

Постановка задачи

Что такое deg~1/3(AC0) ? (Константа 1/3 произвольна.)

Заметки

Я столкнулся с этой проблемой в статье Пола Бима и Видада Мачучи «Квантовая сложность запросов AC0». Они говорят

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

Они также упоминают «проблему приблизительной степени AC0» в своих признаниях.

Итак, я полагаю, что раньше была какая-то работа по этой проблеме? Может кто-нибудь указать мне на статью, в которой говорится о проблеме? И каковы наиболее известные верхние и нижние границы?

Что я знаю о проблеме (этот раздел был добавлен в v2 вопроса)

Самая известная верхняя граница которая известна, - это тривиальная верхняя граница . Лучшая нижняя граница, которую я знаю, исходит от нижней оценки Ааронсона и Ши для задач столкновения и различения элементов, которая дает нижнюю границу . (Для строго ограниченных версий , таких как формулы с размером или схемы с глубиной 2 с воротами , мы можем доказать верхнюю границу используя сложность квантового запроса.)п ~ Ω (п2/3)переменного тока0О(п2)О(п2)о(п)deg~1/3(AC0)nΩ~(N2/3)переменный ток0о(N2)о(N2)о(N)

Связанный: пороговая степень (добавлено в v3)

Как указывает Цуёси в комментариях, эта проблема связана с проблемой определения пороговой степени . Пороговая степень функции - это минимальная степень многочлена такого что а . fpf(x)=1переменный ток0епf ( x ) = 0е(Икс)знак равно1п(Икс)>0е(Икс)знак равно0п(Икс)<0

Нижние оценки пороговой степени теперь улучшены Шерстовым. Он демонстрирует семейство формул с постоянной глубиной для однократного чтения по переменным, пороговая степень которых приближается к мере того, как глубина переходит в бесконечность, что почти тесно, поскольку формулы для однократного чтения имеют порог (и даже приблизительный ) степень . См. Http://eccc.hpi-web.de/report/2014/009/ . (Январь 2014 г.)AС0NΩ(N)О(N)

Робин Котари
источник
7
Нижняя граница Ω (n ^ (1/3)) известна даже для пороговой степени (минимальной степени многочлена p, такого что f (x) = 1 ⇒ p (x)> 0 и f (x) = 0 ⇒ р (х) <0). См. Конец раздела 3.1 «Нижние оценки связи с использованием двойных полиномов» Шерстова .
Tsuyoshi Ito
4
@Tsuyoshi: Спасибо. Пороговая степень (которая ограничивает приблизительную степень) AC0 также является интересным вопросом. Наилучшие нижние оценки, которые я знаю для пороговой степени AC0, заключаются в оценках Новой степени для полиномиальных пороговых функций О'Доннелла и Серведио. Нижняя граница лучше, чем Ω (n ^ (1/3)) по логарифмическому коэффициенту, который увеличивается с глубиной контура.
Робин Котари
4
Упс, вы правы, нижняя граница степени аппроксимации для AC0 очевидна из Ааронсона и Ши. Я такой глупый. Спасибо за указатель на О'Доннелла и Серведио тоже. Ω~(N2/3)
Цуёси Ито
В недавней работе Марка Бана и Джастина Талера под названием «Усиление твердости и приблизительная степень контуров с постоянной глубиной» также кратко обсуждается эта проблема. Они говорят, что нижняя граница Ааронсона и Ши является самой известной нижней границей для функции в AC <sup> 0 </ sup>, и что нижняя граница имеет место даже в немного более общей модели.
Робин Котари

Ответы:

4

Совсем недавно (в середине марта 2017 г.) на ECCC была опубликована статья Марка Бана и Джастина Талера, которая точно отвечает на этот вопрос: «Почти оптимальная нижняя граница для приблизительной степени AC0».

Они утверждают , что для любого , существует функция F в A C 0 такое , что ~ д е г 1 / 3 ( е ) = Ω ( п 1 - δ ) , практически ликвидировать разрыв с тривиальной O ( п ) верхняя граница. Они достигают этого с помощью общего метода для увеличения приблизительной степени функции с сублинейной приблизительной степенью, сохраняя число переменных квазилинейным. Из аннотации:δ>0еAС0dег~1/3(е)знак равноΩ(N1-δ)О(N)

В частности, показано , как преобразовать любую булеву функцию с приблизительной степени д в функцию F на O ( п р о л у л о г ( п ) ) переменных с приблизительной степени по крайней мере , D = Q , ( п 1 / 3 · д 2 / 3 ) . В частности, если , то полиномиально больше, чем . Более того, еслиеdFО(NпоLYLог(N))Dзнак равноΩ(N1/3·d2/3)dзнак равноN1-Ω(1)Ddевычисляются с помощью полиномиального размера булевой схемы постоянной глубины, то и .F

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

Отказ от ответственности: я еще не читал газету внимательно.

A.N.
источник
Действительно, это почти закрывает проблему. Они также показывают DNF квазиполиномиального размера с приблизительной степенью . Ω(N1-δ)
Робин Котари