Теорема о чувствительности ⇐ Васина Википедия

[wiki_en]

Что касается вычислительной сложности, то теорема чувствительности, доказанная Хао Хуаном (математиком) | Хао Хуаном в 2019 году,
==Фон==

Несколько статей конца 1980-х - начала 1990-х годов.
Нисан и Сегеди спросили:
За прошедшие годы было доказано несколько особых случаев гипотезы о чувствительности. Теорема о чувствительности была наконец полностью доказана Хуаном:
==Заявление==

Любая булева функция f\colon \{0,1\}^n \to \{0,1\ может быть выражена уникальным образом в виде полилинейного многочлена. «Степень» f — это степень этого уникального многочлена, обозначаемого \deg(f).

«Чувствительность» булевой функции f в точке x \in \{0,1\}^n равна количеству индексов i \ в [n] такой, что f(x^{\oplus i}) \neq f(x), где x^{\oplus i получается из x путем переворота i-й координаты. Чувствительность f — это максимальная чувствительность f в любой точке x \in \{0,1\}^n, обозначаемая s(f).

Теорема о чувствительности утверждает, что
:s(f) \ge \sqrt{\deg(f)}.
В другую сторону, Таль, :s(f) \leq \deg(f)^2.

Теорема о чувствительности точна для функции И-ИЛИ: :\bigwedge_{i=1}^m \bigvee_{j=1}^m x_{ij}
Эта функция имеет степень m^2 и чувствительность m.

== Доказательство ==

Пусть f\colon \{0,1\}^n \to \{0,1\ — булева функция степени d. Рассмотрим любой «максоном» от f, то есть моном степени d в уникальном полилинейном многочлене, представляющем f. Если мы подставим произвольное значение в координаты, не упомянутые в мономе, то мы получим функцию F по координатам d, имеющую степень d, и более того, s(f) \geq s(F). Если мы докажем теорему о чувствительности для F, то она будет получена и для f. Итак, с этого момента мы без потери общности предполагаем, что f имеет степень n.

Определите новую функцию g\colon \{0,1\}^n \to \{0,1\ с помощью
:g(x_1,\dots,x_n) = f \oplus x_1 \oplus \cdots \oplus x_n.

Хуан
Пусть A — подписанная матрица смежности, соответствующая подписи. Свойство, согласно которому произведение знаков в каждом квадрате равно -1, подразумевает, что A^2=nI, и, следовательно, половина собственных значений A > составляют \sqrt{n}, а половина — -\sqrt{n}. В частности, собственное пространство \sqrt{n} (размерность которого 2^{n-1}) пересекает пространство векторов, поддерживаемых S (который имеет размерность >2^{n-1}), подразумевая, что существует собственный вектор v для A с собственным значением \sqrt{n}, который поддерживается в S. (Это упрощение первоначального аргумента Хуана, приведённого Шалевом Бен-Давидом.
Рассмотрим точку x \in S, максимизирующую |v_x|. С одной стороны, Av = \sqrt{n}v.
С другой стороны, Av — это не более чем сумма абсолютных значений всех соседей x в S, что не более чем \deg_G(x) \cdot |v_x|. Следовательно, \deg_G(x) \geq \sqrt{n}.

===Построение подписи===

Хуан подпись Q_{n+1} следующим образом. Разделите Q_{n+1} на две копии Q_n. Используйте \sigma_n для одного из них и -\sigma_n для другого и присвойте всем ребрам между двумя копиями знак 1.

То же самое подписание может быть выражено и напрямую. Пусть (x,y) — ребро гиперкуба. Если i — первая координата, по которой x,y отличаются, мы используем знак (-1)^{x_1 + \cdots + x_{i-1 .

==Расширения==

Теорему о чувствительности можно эквивалентно переформулировать как
: \deg(f) \leq s(f)^2.
Лапланте и др. : \deg(f) \leq s_0(f)s_1(f),
где s_b(f) — максимальная чувствительность f в точке в f^{-1}(b).
Кроме того, они показали, что эта граница достигается в двух соседних точках гиперкуба.

Ааронсон, Бен-Давид, Котари и Таль * \deg(f) \leq \lambda(f)^2.
* \lambda(f) \leq s(f).
Используя эту меру, они доказали несколько тесных связей между мерами сложности булевых функций: \deg(f) = O(Q(f)^2) и D(f) = O(Q (е)^4). Здесь D(f) — сложность детерминированного запроса, а Q(f) — квантовая сложность запроса.

Дафни и др.
==См. также==
* Модель дерева решений

==Примечания==

* * * * * * * * * * * * * * * * * * * *
Теория сложности вычислений