Теорема о чувствительности

По вычислительной сложности теорема чувствительности , доказанная Хао Хуаном в 2019 году, утверждает, что чувствительность булевой функции $f\colon \{0,1\}^{n}\to \{0,1\}$ является, по крайней мере, квадратным корнем из своей степени , что подтверждает гипотезу, выдвинутую Нисаном и Сегеди в 1992 году. Доказательство особенно лаконично, учитывая, что предыдущий прогресс был ограниченным.

Фон

Несколько статей конца 1980-х - начала 1990-х годов. показал, что различные меры сложности дерева решений булевых функций полиномиально связаны, а это означает, что если $\alpha (f),\beta (f)$ тогда две таких меры $\alpha (f)\leq C\beta (f)^{C}$ для некоторой константы $C>0$. Нисан и Сегеди показал, что степень и приблизительная степень также полиномиально связаны со всеми этими мерами. Их доказательство использовало еще одну меру сложности — блочную чувствительность , введенную Нисаном. Блочная чувствительность обобщает появившуюся ранее более естественную меру (критическую) чувствительность.

Нисан и Сегеди спросили: ограничена ли чувствительность блока полиномиальной чувствительностью (другое направление является непосредственным, поскольку чувствительность не превышает чувствительности блока). Это эквивалентно вопросу, связана ли чувствительность полиномиально с различными мерами сложности дерева решений, а также со степенью, приблизительной степенью и другими мерами сложности, которые, как было показано, полиномиально связаны с ними на протяжении многих лет. Это стало известно как гипотеза чувствительности.

За прошедшие годы было доказано несколько особых случаев гипотезы о чувствительности. Теорема о чувствительности была наконец полностью доказана Хуаном: с помощью редукции Гоцмана и Линиала.

Заявление

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

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

Теорема о чувствительности утверждает, что

$s(f)\geq {\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}.$

Можно показать, что поскольку $f$ имеет степень $n$ затем $g$ несбалансирован (это означает, что $|g^{-1}(0)|\neq |g^{-1}(1)|$), сказать $|g^{-1}(1)|>2^{n-1}$. Рассмотрим подграф $G$ гиперкуба (график на $\{0,1\}^{n}$ в котором две вершины соединены, если они отличаются одной координатой), индуцированной $S=g^{-1}(1)$. Для доказательства теоремы о чувствительности достаточно показать, что $G$ имеет вершину, степень которой не меньше ${\sqrt {n}}$. Это сокращение принадлежит Гоцману и Линиалу.

Хуан строит подпись гиперкуба , в которой произведение знаков вдоль любого квадрата равно $-1$. Это означает, что существует способ присвоить знак каждому ребру гиперкуба, чтобы это свойство выполнялось. Такая же подпись была обнаружена ранее Ахмади и др., которые интересовались подписанием графов с несколькими различными собственными значениями.

Позволять $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}}$.

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

Хуан построил подпись рекурсивно. Когда $n=1$, мы можем взять произвольную подпись. Учитывая подписание $\sigma _{n}$ принадлежащий $n$-мерный гиперкуб $Q_{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)$. Кроме того, они показали, что эта граница достигается в двух соседних точках гиперкуба.

Ааронсон, Бен-Давид, Котари и Таль определил новую меру — чувствительность спектральную $f$, обозначенный $\lambda (f)$. Это наибольшее собственное значение матрицы смежности чувствительности графа $f$, который является подграфом гиперкуба, состоящим из всех чувствительных ребер (ребер, соединяющих две точки $x,y$ такой, что $f(x)\neq f(y)$). Они показали, что доказательство Хуанга можно разбить на два этапа:

• $\deg(f)\leq \lambda (f)^{2}$.
• $\lambda (f)\leq s(f)$.

Используя эту меру, они доказали несколько тесных связей между мерами сложности булевых функций: $\deg(f)=O(Q(f)^{2})$ и $D(f)=O(Q(f)^{4})$. Здесь $D(f)$ - это детерминированная сложность запроса и $Q(f)$ — сложность квантового запроса.

Дафни и др. расширил понятия степени и чувствительности на булевы функции на симметричной группе и на идеального паросочетания схеме ассоциации и доказал аналоги теоремы о чувствительности для таких функций. Их доказательства используют редукцию к теореме Хуанга о чувствительности.

См. также

• Модель дерева решений

Ссылки

• Ааронсон, Скотт; Бен-Давид, Шалев; Котари, Робин; Рао, Шравас; Таль, Авишай (15 июня 2021 г.). Степень против приблизительной степени и квантовые последствия теоремы Хуанга о чувствительности . АКМ. стр. 1330–1342. arXiv : 2010.12629 . дои : 10.1145/3406325.3451047 . ISBN  978-1-4503-8053-9 .
• Ахмади, Бахман; Алинагипур, Фатима; Каверс, Майкл С.; Фаллат, Шон; Мигер, Карен; Нассераср, Шахла (сентябрь 2013 г.). «Минимальное количество различных собственных значений графов» Электронный журнал линейной алгебры . 26 . Международное общество линейной алгебры: 673–691. дои : 10.13001/1081–3810.1679 . ISSN   1081-3810 .
• Бафна, Митали; Локам, Сатьянараяна В.; Тавенас, Себастьен; Велинкер, Амейя; Фалишевский, Петр; Мусхолл, Анка; Нидермайер, Рольф (2016). «О гипотезе чувствительности для формул Read -k ». 41-й Международный симпозиум по математическим основам информатики (MFCS 2016) . п. 14 страниц. doi : 10.4230/LIPICS.MFCS.2016.16 . ISSN   1868-8969 .
• Дафни, Нета; Фильмус, Юваль; Лифшиц, Ноам; Линдзи, Натан; Виньялс, Марк; Ли, Джеймс Р. (2021). «Меры сложности в симметричной группе и за ее пределами (расширенное резюме)». 12-я конференция «Инновации в теоретической информатике (ITCS)» . п. 5 страниц, 326343 байт. doi : 10.4230/LIPICS.ITCS.2021.87 . ISSN   1868-8969 .
• Бен-Давид, Шалев (3 июля 2019 г.). «Комментарий № 35 к гипотезе о чувствительности решен» .
• Блюм, Мануэль; Импальяццо, Рассел (1987). «Общие оракулы и классы оракулов». 28-й ежегодный симпозиум по основам информатики (SFC, 1987) . IEEE. дои : 10.1109/sfcs.1987.30 .
• Бурман, Гарри; де Вольф, Рональд (2002). «Меры сложности и сложность дерева решений: обзор». Теоретическая информатика . 288 (1). Эльзевир Б.В.: 21–43. дои : 10.1016/s0304-3975(01)00144-x . ISSN   0304-3975 .
• CS, Картик; Тавенас, Себастьен; Лал, Акаш; Акшай, С.; Саураб, Сакет; Сен, Сандип (2016). «О гипотезе чувствительности дизъюнктивных нормальных форм». 36-я ежегодная конференция IARCS по основам программных технологий и теоретической информатики (FSTTCS 2016) . п. 15 страниц. doi : 10.4230/LIPICS.FSTTCS.2016.15 . ISSN   1868-8969 .
• Кук, Стивен; Дворк, Синтия; Рейщук, Рюдигер (1986). «Верхняя и нижняя границы времени для параллельных машин произвольного доступа без одновременной записи». SIAM Journal по вычислительной технике . 15 (1): 87–97. дои : 10.1137/0215006 . ISSN   0097-5397 .
• Гоцман, Хаим; Линиал, Нати (1992). «Эквивалентность двух задач на кубе» . Журнал комбинаторной теории, серия А. 61 (1). Эльзевир Б.В.: 142–146. дои : 10.1016/0097-3165(92)90060-8 . ISSN   0097-3165 .
• Хартманис, Юрис; Хемачандра, Лейн А. (1991). «Односторонние функции и неизоморфизм NP-полных множеств» . Теоретическая информатика . 81 (1): 155–163. дои : 10.1016/0304-3975(91)90323-T .
• Хатами, Пуя; Кулкарни, Рагхав; Панкратов, Денис (2011). «Вариации гипотезы о чувствительности» . Теория вычислений . 1 (1): 1–27. дои : 10.4086/toc.gs.2011.004 . ISSN   1557-2862 .
• Хуан, Хао (01 ноября 2019 г.). «Индуцированные подграфы гиперкубов и доказательство гипотезы чувствительности». Анналы математики . 190 (3). arXiv : 1907.00847 . дои : 10.4007/анналы.2019.190.3.6 . ISSN   0003-486X .
• Кларрайх, Эрика (25 июля 2019 г.). «Гипотеза десятилетней компьютерной науки решена на двух страницах» . Журнал Кванта .
• Лаплант, Софи; Насераср, Реза; Санни, Анупа; Ван, Чжоунингсинь (07 марта 2023 г.). «Гипотеза о чувствительности и знаковые гиперкубы» . Архив открытого HAL . Проверено 25 апреля 2024 г.
• Нисан, Ноам (1991). «коляски экипажа и деревья решений». SIAM Journal по вычислительной технике . 20 (6): 999–1007. дои : 10.1137/0220062 . ISSN   0097-5397 .
• Нисан, Ноам; Сегеди, Марио (1994). «О степени булевых функций как вещественных многочленов». Вычислительная сложность . 4 (4): 301–313. дои : 10.1007/BF01263419 . ISSN   1016-3328 .
• Саймон, Ганс-Ульрих (1983). «Точная Ω(loglog n)-оценка времени для параллельных вычислений Ram для вычисления невырожденных логических функций». Основы теории вычислений . Конспекты лекций по информатике. Том. 158. Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 439–444. дои : 10.1007/3-540-12689-9_124 . ISBN  978-3-540-12689-8 .
• Таль, Авишай (9 января 2013 г.). «Свойства и применение композиции логических функций». ITCS '13: Материалы 4-й конференции «Инновации в теоретической информатике» . АКМ. дои : 10.1145/2422436.2422485 . ISBN  978-1-4503-1859-4 .
• Тардос, Г. (1989). «Сложность запроса, или почему сложно разделить $NP^{A}\cap coNP^{A}$ от $P^{A}$ случайными оракулами $A$?". Combinatorica . 9 (4): 385–392. doi : 10.1007/BF02125350 . ISSN   0209-9683 .
• Вегенер, Инго (1987). Сложность булевых функций . Штутгарт Чичестер Нью-Йорк Брисбен [и др.]: John Wiley & Sons. ISBN  0-471-91555-6 .