Машине предоставляется оракулу доступ к случайной булевой функции и двум спектрам Фурье и .
Спектры Фурье функции определяются как :
Один из или является истинным спектром Фурье для а другой - просто фиктивным спектром Фурье, принадлежащим неизвестной случайной булевой функции.
Нетрудно показать, что машина не может даже приблизить для любых .
Какова сложность запроса в определении с высокой вероятностью успеха, какой из них является истинным?
Мне интересно, так как если эта проблема не в , то можно показать, что существует оракул, относительно которого не является подмножеством .
cc.complexity-theory
lg.learning
boolean-functions
fourier-analysis
Мирмойтаба Гариби
источник
источник
Ответы:
Извините, я опоздал - это замечательный вопрос! Как уже отмечали другие, именно поэтому я задал вопрос в своей статье BQP vs. PH , и поэтому я потратил 4 или 5 месяцев, работая над этим безуспешно, еще в 2008 году. Одним из способов ответить на этот вопрос было бы доказать гораздо более общее утверждение, которое я назвал «Обобщенной гипотезой Линиала-Нисана», но, к сожалению, эта гипотеза оказалась ложной , по крайней мере, для контуров глубины 3 и выше. (Я все еще думаю, что это, вероятно, верно для схем глубины 2, которые, по крайней мере, привели бы к разделению оракула между BQP и AM.) Для более поздних идей (самых последних, насколько я знаю) к разделению оракула между BQP и PH, посмотрите хорошую статью Феффермана, Шалтиэля, Уманса,
источник
Скотт Ааронсон может быть лучшим человеком в мире, чтобы ответить на этот вопрос, возможно, у него будет лучший ответ после того, как этот вопрос будет опубликован. он предложил исходную проблему, о которой этот опубликованный вопрос, кажется, очень слабый вариант, так называемая проблема проверки Фурье (более подробно об этом в комментариях). проблема тесно связана / почти эквивалентна разделению двух важных классов сложности PH и BQP, что является ключевой открытой проблемой теории сложности КМ, и, по-видимому, она очень сложна. Похоже, что до сих пор кто-то, кроме Ааронсона, и, возможно, даже не он, провел много прямых / дальнейших исследований этой проблемы по этой проблеме (по-видимому, ей чуть больше двух лет).
однако здесь есть по крайней мере одна статья, написанная кем-то кроме Ааронсона, которая фокусируется / строит на гипотезе / проблеме с некоторыми новыми результатами.
Экспоненциальные ускорения являются общими для Фернандо GSL Brandão и Михаила Городецкого
источник