РЕДАКТИРОВАТЬ (v2): в конце добавлен раздел о том, что я знаю о проблеме.
РЕДАКТИРОВАТЬ (v3): Добавлено обсуждение пороговой степени в конце.
Вопрос
Этот вопрос в основном справочный запрос. Я не знаю много о проблеме. Я хочу знать, была ли предыдущая работа по этой проблеме, и если да, может ли кто-нибудь указать мне какие-либо статьи, в которых говорится об этой проблеме? Я также хотел бы знать текущие лучшие оценки приблизительной степени . Любая другая информация также будет оценена (например, историческая информация, мотивация, отношение к другим проблемам и т. Д.).
Определения
Пусть - булева функция. Пусть - многочлен от переменных до с действительными коэффициентами. Степень многочлена является максимальной степенью по всем мономам. Степень монома - это сумма показателей различных которые появляются в этом мономе. Например, .p x 1 x n x i deg ( x 7 1 x 2 3 ) = 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 ) | < ϵϵ f ~ deg ϵ ( f ) ϵ f F ~ deg ϵ ( F ) d Fд,
Обратите внимание, что каждая функция может быть представлена без ошибок полиномом степени . Некоторые функции действительно нуждаются в полиноме степени чтобы приблизиться к любой постоянной ошибке. Паритет является примером такой функции.
Постановка задачи
Что такое ? (Константа 1/3 произвольна.)
Заметки
Я столкнулся с этой проблемой в статье Пола Бима и Видада Мачучи «Квантовая сложность запросов AC0». Они говорят
Кроме того, наши результаты не делают ничего, чтобы закрыть разрыв в нижней границе приблизительной степени функций AC0.
Они также упоминают «проблему приблизительной степени AC0» в своих признаниях.
Итак, я полагаю, что раньше была какая-то работа по этой проблеме? Может кто-нибудь указать мне на статью, в которой говорится о проблеме? И каковы наиболее известные верхние и нижние границы?
Что я знаю о проблеме (этот раздел был добавлен в v2 вопроса)
Самая известная верхняя граница которая известна, - это тривиальная верхняя граница . Лучшая нижняя граница, которую я знаю, исходит от нижней оценки Ааронсона и Ши для задач столкновения и различения элементов, которая дает нижнюю границу . (Для строго ограниченных версий , таких как формулы с размером или схемы с глубиной 2 с воротами , мы можем доказать верхнюю границу используя сложность квантового запроса.)п ~ Ω (п2/3)переменного тока0О(п2)О(п2)о(п)
Связанный: пороговая степень (добавлено в v3)
Как указывает Цуёси в комментариях, эта проблема связана с проблемой определения пороговой степени . Пороговая степень функции - это минимальная степень многочлена такого что а . fpf(x)=1f ( x ) = 0
Нижние оценки пороговой степени теперь улучшены Шерстовым. Он демонстрирует семейство формул с постоянной глубиной для однократного чтения по переменным, пороговая степень которых приближается к мере того, как глубина переходит в бесконечность, что почти тесно, поскольку формулы для однократного чтения имеют порог (и даже приблизительный ) степень . См. Http://eccc.hpi-web.de/report/2014/009/ . (Январь 2014 г.)
Ответы:
Совсем недавно (в середине марта 2017 г.) на ECCC была опубликована статья Марка Бана и Джастина Талера, которая точно отвечает на этот вопрос: «Почти оптимальная нижняя граница для приблизительной степени AC0».
Они утверждают , что для любого , существует функция F в A C 0 такое , что ~ д е г 1 / 3 ( е ) = Ω ( п 1 - δ ) , практически ликвидировать разрыв с тривиальной O ( п ) верхняя граница. Они достигают этого с помощью общего метода для увеличения приблизительной степени функции с сублинейной приблизительной степенью, сохраняя число переменных квазилинейным. Из аннотации:δ> 0 е A C0 д е г~1 / 3( ф) = Ω ( n1 - δ) O ( n )
Это последнее обновление в нижней части этой проблемы, и это довольно значительный шаг вперед. Разделы «Введение» и «Применение» также являются хорошими источниками ссылок на предыдущие работы и связанные с ними проблемы.
Отказ от ответственности: я еще не читал газету внимательно.
источник