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

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

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

Решение дерева модель играет важная роль в установлении нижних оценок для теории сложности для некоторых классов вычислительных задач и алгоритмов. Было введено несколько вариантов моделей дерева решений, в зависимости от вычислительной модели и типа алгоритмов запросов, которые разрешено выполнять.

Например, дерево решений аргумента используется , чтобы показать , что сравнение рода из пунктов должен сравнивать. Для сортировок сравнения запрос - это сравнение двух элементов с двумя результатами (при условии, что нет равных элементов): либо, либо . Сортировки сравнения могут быть выражены в виде дерева решений в этой модели, поскольку такие алгоритмы сортировки выполняют только эти типы запросов. $n$ $n\log(n)$ $a,\,b$ $a<b$ $a>b$

Деревья сравнения и нижние границы для сортировки [ править ]

Деревья решений часто используются для понимания алгоритмов сортировки и других подобных проблем; это было впервые сделано Фордом и Джонсоном. ^[1]

Например, многие алгоритмы сортировки являются сравнение сортов , что означает , что они только получить информацию о последовательности входных данных с помощью локальных сравнений: тестирование ли , или . Если предположить, что элементы, которые нужно отсортировать, различны и сопоставимы, это можно перефразировать как вопрос типа «да» или «нет»: есть ли? $x_{1},x_{2},\ldots ,x_{n}$ $x_{i}<x_{j}$ $x_{i}=x_{j}$ $x_{i}>x_{j}$ $x_{i}>x_{j}$

Эти алгоритмы могут быть смоделированы как двоичные деревья решений, где запросы являются сравнениями: внутренний узел соответствует запросу, а дочерние узлы соответствуют следующему запросу, когда ответ на вопрос - да или нет. Для конечных узлов выходные данные соответствуют перестановке , описывающей, как входная последовательность была скремблирована из полностью упорядоченного списка элементов. (Обратный к этой перестановке , переупорядочивает входную последовательность.) $\pi$ $\pi ^{-1}$

Можно показать, что сортировки сравнения должны использовать сравнения с помощью простого аргумента: для того, чтобы алгоритм был правильным, он должен иметь возможность выводить все возможные перестановки элементов; в противном случае алгоритм не сможет использовать эту конкретную перестановку в качестве входных данных. Таким образом, соответствующее дерево решений должно иметь как минимум столько же листьев, сколько и перестановок: листьев. Любое двоичное дерево с как минимум листьями имеет глубину как минимум , так что это нижняя граница времени выполнения алгоритма сортировки сравнения. В этом случае существование множества алгоритмов сравнения-сортировки, имеющих такую временную сложность, таких как сортировка слиянием и heapsort , демонстрирует, что граница жесткая. ^[2]^:⁹¹ $\Omega (n\log(n))$ $n$ $n!$ $n!$ $\log _{2}(n!)=\Omega (n\log _{2}(n))$

В этом аргументе ничего не говорится о типе запроса, поэтому он фактически доказывает нижнюю границу для любого алгоритма сортировки, который можно смоделировать как двоичное дерево решений. По сути, это переформулировка теоретико-информационного аргумента о том, что правильный алгоритм сортировки должен узнавать хотя бы биты информации о входной последовательности. В результате это также работает и для рандомизированных деревьев решений. $\log _{2}(n!)$

В других нижних границах дерева решений используется то, что запрос является сравнением. Например, рассмотрим задачу использования только сравнений, чтобы найти наименьшее число среди чисел. Прежде чем можно будет определить наименьшее число, каждое число, кроме наименьшего, должно «проиграть» (сравнить большее) хотя бы в одном сравнении. Итак, чтобы найти минимум , нужно хотя бы сравнения. (Теоретико-информационный аргумент здесь дает только нижнюю границу .) Аналогичный аргумент работает для общих нижних оценок для вычисления статистики порядка . ^[2]^:²¹⁴ $n$ $n-1$ $\log(n)$

Линейные и алгебраические деревья решений [ править ]

Линейные деревья решений обобщают приведенные выше деревья решений сравнения на вычислительные функции, которые принимают на входе действительные векторы . Тесты в линейных деревьях решений являются линейными функциями: для конкретного выбора действительных чисел выведите знак . (Алгоритмы в этой модели могут зависеть только от знака выходных данных.) Деревья сравнения - это линейные деревья решений, потому что сравнение между и соответствует линейной функции . Согласно своему определению, линейные деревья решений могут определять только функции , слои которых могут быть построены путем объединения и пересечения полупространств. $x\in \mathbb {R} ^{n}$ $a_{0},\dots ,a_{n}$ $a_{0}+\textstyle \sum _{i=1}^{n}a_{i}x_{i}$ $x_{i}$ $x_{j}$ $x_{i}-x_{j}$ $f$

Алгебраические деревья решений являются обобщением линейных деревьев решений, которые позволяют тестовым функциям быть полиномами степени . Геометрически пространство разделено на полуалгебраические множества (обобщение гиперплоскости). $d$

Эти модели деревьев решений, определенные Рабином ^[3] и Рейнгольдом ^[4] , часто используются для доказательства нижних оценок в вычислительной геометрии . ^[5] Например, Бен-Ор показал, что уникальность элемента (задача вычисления , где 0 тогда и только тогда, когда существуют различные координаты, такие, что ) требует алгебраического дерева решений глубины . ^[6] Это было впервые показано для моделей линейных решений Добкиным и Липтоном. ^[7] Они также показывают нижнюю оценку для линейных деревьев решений в задаче о рюкзаке, обобщенную Стилом и Яо на алгебраические деревья решений. ^[8] $f:\mathbb {R} ^{n}\to \{0,1\}$ $f(x)$ $i,j$ $x_{i}=x_{j}$ $\Omega (n\log(n))$ $n^{2}$

Сложности логического дерева решений [ править ]

Для булевых деревьев решений задача состоит в том, чтобы вычислить значение n-битной логической функции для входа . Запросы соответствуют чтению бита ввода , а вывод - . Каждый запрос может зависеть от предыдущих запросов. Существует много типов вычислительных моделей, использующих деревья решений, которые можно рассматривать, допуская несколько понятий сложности, называемых мерами сложности . $f:\{0,1\}^{n}\rightarrow \{0,1\}$ $x\in \{0,1\}^{n}$ $x_{i}$ $f(x)$

Детерминированное дерево решений [ править ]

Если результат дерева решений для всех , дерево решений называется «вычисляющим» . Глубина дерева - это максимальное количество запросов, которое может произойти до того, как будет достигнут лист и получен результат. , сложность детерминированного дерева решений является наименьшей глубиной среди всех вычисляемых детерминированных деревьев решений . $f(x)$ $x\in \{0,1\}^{n}$ $f$ $D(f)$ $f$ $f$

Рандомизированное дерево решений [ править ]

Один из способов определить рандомизированное дерево решений - добавить в дерево дополнительные узлы, каждый из которых управляется вероятностью . Другое эквивалентное определение - определить его как распределение по детерминированным деревьям решений. На основе этого второго определения сложность рандомизированного дерева определяется как наибольшая глубина среди всех деревьев, поддерживающих базовое распределение. определяется как сложность рандомизированного дерева решений с наименьшей глубиной, результат которого с вероятностью по крайней мере для всех (т. е. с ограниченной двусторонней ошибкой). $p_{i}$ $R_{2}(f)$ $f(x)$ $2/3$ $x\in \{0,1\}^{n}$

$R_{2}(f)$ известна как сложность рандомизированного дерева решений Монте-Карло , потому что результат может быть неверным с ограниченной двусторонней ошибкой. Лас - Вегас сложность принятия дерева измеряет ожидаемую глубину дерева решений , которое должно быть правильным (т.е., имеет нулевую ошибку). Существует также версия с односторонней ограниченной ошибкой, которая обозначается как . $R_{0}(f)$ $R_{1}(f)$

Дерево недетерминированных решений [ править ]

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

Формально сложность сертификата at - это размер наименьшего подмножества индексов, таких что для всех , если для всех , то . Сложность сертификата - это максимальная сложность сертификата . Обозначено аналогичное понятие, в котором требуется, чтобы проверяющий был прав с вероятностью 2/3 . $f$ $x$ $S\subset [n]$ $y\in \{0,1\}^{n}$ $y_{i}=x_{i}$ $i\in S$ $f(y)=f(x)$ $f$ $x$ $RC(f)$

Квантовое дерево решений [ править ]

Сложность квантового дерева решений - это глубина квантового дерева решений самой низкой глубины, которая дает результат с вероятностью по крайней мере для всех . Другая величина,, определяется как глубина квантового дерева решений с наименьшей глубиной, которое дает результат с вероятностью 1 во всех случаях (т.е. вычисляется точно). и более известны как сложность квантовых запросов , потому что прямое определение дерева квантовых решений сложнее, чем в классическом случае. Как и в случайном случае, мы определяем и . $Q_{2}(f)$ $f(x)$ $2/3$ $x\in \{0,1\}^{n}$ $Q_{E}(f)$ $f(x)$ $f$ $Q_{2}(f)$ $Q_{E}(f)$ $Q_{0}(f)$ $Q_{1}(f)$

Эти понятия обычно ограничиваются понятиями степени и приблизительной степени. Степени из , обозначенная , является наименьшая степень любого многочлена , удовлетворяющего для всех . Приблизительная степень из , обозначенная , является наименьшая степень любого полинома , удовлетворяющего всякий раз , когда и когда . $f$ $\operatorname {deg} (f)$ $p$ $f(x)=p(x)$ $x\in \{0,1\}^{n}$ $f$ ${\widetilde {\operatorname {deg} }}(f)$ $p$ $p(x)\in [0,1/3]$ $f(x)=0$ $p(x)\in [2/3,1]$ $f(x)=1$

Beals et al. установил, что и . ^[9] $Q_{0}(f)\geq \operatorname {deg} (f)/2$ $Q_{2}(f)\geq {\widetilde {\operatorname {deg} }}(f)/2$

Взаимосвязи между мерами сложности логических функций [ править ]

Непосредственно из определений следует , что для всех битовых булевых функций , и . Поиск лучших верхних границ в обратном направлении - основная цель в области сложности запросов. $n$ $f$ $Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n$ $Q_{2}(f)\leq Q_{0}(f)\leq D(f)\leq n$

Все эти типы сложности запроса полиномиально связаны. Это независимо друг от друга обнаружили Блюм и Импальяццо ^[10], Хартманис и Хемачандра ^[11] и Тардос ^[12] . Ноам Нисан обнаружил , что Монте - Карло рандомизированы сложность дерева решений также полиномиально связаны с детерминированным решением сложности дерева: . ^[13] (Нисан также показал , что .) Более плотно связь известна между моделями Монте - Карло и Лас - Вегас: . ^[14] Это соотношение оптимально с точностью до полилогарифмических факторов. ^[15] Что касается сложностей квантового дерева решений, и эта граница жесткая. ^[16]^[15] $D(f)\leq R_{0}(f)^{2}$ $D(f)=O(R_{2}(f)^{3})$ $D(f)=O(R_{1}(f)^{2})$ $R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))$ $D(f)=O(Q_{2}(f)^{4})$ Midrijanis показал , что , ^[17]^[18] повышение квартика связанные в связи с Билсом и др. ^[9] $D(f)=O(Q_{0}(f)^{3})$

Важно отметить, что эти полиномиальные отношения действительны только для полных булевых функций. Для частичных булевых функций , у которых есть область подмножества , возможно экспоненциальное разделение между и ; первый пример такой проблемы был обнаружен Дойчем и Йозой . $\{0,1\}^{n}$ $Q_{0}(f)$ $D(f)$

Гипотеза о чувствительности [ править ]

Для булевой функции , то чувствительность из определяются как максимальная чувствительность по всем , где чувствительности при этом количестве однобитовых изменений в этом изменить значение . Чувствительность связана с понятием общего влияния анализа булевых функций , которое равно средней чувствительности по всем параметрам . $f:\{0,1\}^{n}\to \{0,1\}$ $f$ $f$ $x$ $f$ $x$ $x$ $f(x)$ $x$

Гипотеза о чувствительности - это гипотеза о том, что чувствительность полиномиально связана со сложностью запроса; то есть, существует показатель такой , что для всех , и . Это можно показать с помощью простого аргумента , поэтому гипотеза конкретно касается поиска нижней границы чувствительности. Поскольку все ранее обсуждавшиеся меры сложности полиномиально связаны, точный тип меры сложности не имеет значения. Однако это обычно формулируется как вопрос о связи чувствительности с чувствительностью к блоку. $c,c'$ $f$ $D(f)=O(s(f)^{c})$ $s(f)=O(D(f)^{c'})$ $s(f)\leq D(f)$

Чувствительности блока из , обозначается , определяется как максимальная чувствительность блока над всем . Чувствительность блока at - это максимальное количество непересекающихся подмножеств , так что для любого из подмножеств переключение битов, соответствующих изменению, изменяет значение . ^[13] $f$ $bs(f)$ $f$ $x$ $f$ $x$ $t$ $S_{1},\ldots ,S_{t}\subset [n]$ $S_{i}$ $x$ $S_{i}$ $f(x)$

Поскольку чувствительность блока занимает максимум за более широкий выбор подмножеств, . Кроме того, чувствительность к блокам полиномиально связана с ранее обсужденными мерами сложности; например, статья Нисана о чувствительности к блокам показала это . ^[13] Таким образом, можно было бы перефразировать гипотезу чувствительности , как показывает , что для некоторых , . В 1992 году Нисан и Сегеди предположили, что этого достаточно. ^[19] Это было бы сложно, поскольку Рубинштейн в 1995 году показал квадратичное разделение между чувствительностью и чувствительностью к блоку. ^[20] $s(f)\leq bs(f)$ $bs(f)\leq D(f)=O(bs(f)^{4})$ $c$ $bs(f)=O(s(f)^{c})$ $c=2$

В июле 2019 года, через 27 лет после первоначального высказывания гипотезы, Хао Хуан из Университета Эмори доказал гипотезу о чувствительности, продемонстрировав это . ^[21] Это доказательство особенно лаконично, доказывая это утверждение на двух страницах, когда предыдущий прогресс в отношении гипотезы о чувствительности был ограничен. ^[22]^[23] $bs(f)=O(s(f)^{4})$

Сводка известных результатов [ править ]

Наиболее известные разделения по комплексным мерам по состоянию на октябрь 2020 г. ^[16]^[update]
	$D$	$R_{0}$	$R_{2}$	$C$	$RC$	$bs$	$s$	$Q_{0}$	$\operatorname {deg}$	$Q$	${\widetilde {\operatorname {deg} }}$
$D$		2	2, 3	2	2, 3	2, 3	3, 6	2, 3	2, 3	4	4
$R_{0}$	1		2	2	2, 3	2, 3	3, 6	2, 3	2, 3	3, 4	4
$R$	1	1		2	2, 3	2, 3	3, 6	1,5, 3	2, 3	3, 4	4
$C$	1	1	1, 2		2	2	2,22, 5	1,15, 3	1,63, 3	2, 4	2, 4
$RC$	1	1	1	1		1,5, 2	2, 4	1,15, 2	1,63, 2	2	2
$bs$	1	1	1	1	1		2, 4	1,15, 2	1,63, 2	2	2
$s$	1	1	1	1	1	1		1,15, 2	1,63, 2	2	2
$Q_{0}$	1	1,33, 2	1,33, 3	2	2, 3	2, 3	3, 6		2, 3	2, 4	4
$\operatorname {deg}$	1	1,33, 2	1,33, 2	2	2	2	2	1		2	2
$Q$	1	1	1	2	2, 3	2, 3	3, 6	1	2, 3		4
${\widetilde {\operatorname {deg} }}$	1	1	1	2	2	2	2	1	1	1

В этой таблице приведены результаты по разделению мер сложности булевых функций. Меры сложности: детерминированный, рандомизированный с нулевой ошибкой, рандомизированный с двусторонней ошибкой, сертификат, рандомизированный сертификат, чувствительность блока, чувствительность, точная величина, степень, квант и приблизительная степень сложности.

Число в -й строке и -м столбце обозначает границы экспоненты , которая представляет собой точную нижнюю грань всех удовлетворяющих всем логическим функциям . Например, запись в строке D и столбце s - «3, 6», так что для всех существует такая функция , что . $A$ $B$ $c$ $k$ $A(f)=O(B(f)^{k})$ $f$ $D(f)=O(\operatorname {s} (f)^{6+o(1)})$ $f$ $g$ $D(g)=\Omega (\operatorname {s} (g)^{3-o(1)})$

См. Также [ править ]

Сравнительная сортировка
Древо решений
Гипотеза Андераа – Карпа – Розенберга
Минимальное остовное дерево # Деревья решений

Ссылки [ править ]

^ Младший, Лестер Р. Форд; Джонсон, Селмер М. (1959-05-01). «Турнирная задача» . Американский математический ежемесячник . 66 (5): 387–389. DOI : 10.1080 / 00029890.1959.11989306 . ISSN 0002-9890 .
^ a b Введение в алгоритмы . Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. ISBN. 978-0-262-27083-0. OCLC 676697295 .CS1 maint: others (link)
^ Рабин, Майкл О. (1972-12-01). «Доказательство одновременной положительности линейных форм» . Журнал компьютерных и системных наук . 6 (6): 639–650. DOI : 10.1016 / S0022-0000 (72) 80034-5 . ISSN 0022-0000 .
^ Рейнгольд, Эдвард М. (1972-10-01). «Об оптимальности некоторых алгоритмов множества» . Журнал ACM . 19 (4): 649–659. DOI : 10.1145 / 321724.321730 . ISSN 0004-5411 . S2CID 18605212 .
^ Препарата, Франко П. (1985). Вычислительная геометрия: введение . Шамос, Майкл Ян. Нью-Йорк: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840 .
^ Бен-Ор, Майкл (1983-12-01). «Нижние оценки для алгебраических вычислительных деревьев» . Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений . СТОК '83. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники: 80–86. DOI : 10.1145 / 800061.808735 . ISBN 978-0-89791-099-6. S2CID 1499957 .
↑ Добкин, Дэвид; Липтон, Ричард Дж. (1976-06-01). «Многомерные поисковые задачи» . SIAM Journal on Computing . 5 (2): 181–186. DOI : 10.1137 / 0205015 . ISSN 0097-5397 .
^ Майкл Стил, J; Яо, Эндрю К. (1982-03-01). «Нижние оценки для алгебраических деревьев решений» . Журнал алгоритмов . 3 (1): 1–8. DOI : 10.1016 / 0196-6774 (82) 90002-5 . ISSN 0196-6774 .
^ a b Билс, Р .; Buhrman, H .; Умная.; Моска, М .; де Вольф, Р. (2001). «Квантовые оценки снизу по многочленам». Журнал ACM . 48 (4): 778–797. arXiv : квант-ph / 9802049 . DOI : 10.1145 / 502090.502097 . S2CID 1078168 .
^ Блюм, М .; Impagliazzo, Р. (1987). «Общие оракулы и классы оракулов». Труды 18-го IEEE FOCS . С. 118–126.
^ Hartmanis, J .; Хемачандра, Л. (1987), «Односторонние функции, устойчивость и неизоморфизм NP-полных наборов», Технический отчет DCS TR86-796, Корнельский университет
^ Tardos, G. (1989). «Сложность запроса, или почему сложно отделить NP ^A ∩ coNP ^A от P ^A случайными оракулами A ?». Combinatorica . 9 (4): 385–392. DOI : 10.1007 / BF02125350 . S2CID 45372592 .
^ a b c Нисан, Н. (1989). «ЭКИПАЖНЫЕ ПРОГРАММЫ и деревья решений». Материалы 21-го ACM STOC . С. 327–335.
^ Кулькарни, Р. и Тал, А. О чувствительности к дробному блоку. Электронный коллоквиум по вычислительной сложности (ECCC). Vol. 20. 2013.
^ a b Амбаинис, Андрис; Балодис, Каспарс; Беловс, Александр; Ли, Трой; Сантха, Миклош; Смотровы, Юрис (04.09.2017). «Разделение сложности запросов на основе функций указателя» . Журнал ACM . 64 (5): 32: 1–32: 24. arXiv : 1506.04719 . DOI : 10.1145 / 3106234 . ISSN 0004-5411 . S2CID 10214557 .
^ a b Ааронсон, Скотт; Бен-Давид, Шалев; Котари, Робин; Рао, Шравас; Тал, Авишай (2020-10-23). «Степень против приблизительной степени и квантовые последствия теоремы Хуанга о чувствительности». arXiv : 2010.12629 [ квант-ф ].
^ Мидриджанис, Гатис (2004), «Точная квантовая сложность запроса для полных булевых функций», arXiv : Quant-ph / 0403168
^ Мидриджанис, Гатис (2005), «О рандомизированных и квантовых сложностях запросов», arXiv : Quant-ph / 0501142
^ Нисан, Ноам; Сегеди, Марио (1992-07-01). «О степени булевых функций как вещественных многочленов» . Материалы двадцать четвертого ежегодного симпозиума ACM по теории вычислений . СТОК '92. Виктория, Британская Колумбия, Канада: Ассоциация вычислительной техники: 462–467. DOI : 10.1145 / 129712.129757 . ISBN 978-0-89791-511-3. S2CID 6919144 .
^ Рубинштейн, Дэвид (1995-06-01). «Чувствительность против блочной чувствительности булевых функций» . Combinatorica . 15 (2): 297–299. DOI : 10.1007 / BF01200762 . ISSN 1439-6912 . S2CID 41010711 .
^ Хуан, Хао (2019). «Индуцированные подграфы гиперкубов и доказательство гипотезы о чувствительности». Анналы математики . 190 (3): 949–955. arXiv : 1907.00847 . DOI : 10.4007 / annals.2019.190.3.6 . ISSN 0003-486X . JSTOR 10.4007 / annals.2019.190.3.6 . S2CID 195767594 .
^ Кларрайх, Эрика. «Гипотеза десятилетней давности компьютерных наук, решенная на двух страницах» . Журнал Quanta . Проверено 26 июля 2019 .
^ Хатами, Пуйя; Кулкарни, Рагхав; Панкратов, Денис (22.06.2011). «Вариации гипотезы о чувствительности» . Теория вычислений . 1 : 1-27. DOI : 10.4086 / toc.gs.2011.004 . ISSN 1557-2862 . S2CID 6918061 .

Опросы [ править ]

Бурман, Гарри; де Вольф, Рональд (2002), "Меры сложности и принятие решения Сложности: Обзор" (PDF) , теоретическая информатика , 288 (1): 21-43, DOI : 10.1016 / S0304-3975 (01) 00144-X

[1] Младший, Лестер Р. Форд; Джонсон, Селмер М. (1959-05-01). «Турнирная задача» . Американский математический ежемесячник . 66 (5): 387–389. DOI : 10.1080 / 00029890.1959.11989306 . ISSN 0002-9890 .

[CLRS-2] Введение в алгоритмы . Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. ISBN. 978-0-262-27083-0. OCLC 676697295 .CS1 maint: others (link)

[3] Рабин, Майкл О. (1972-12-01). «Доказательство одновременной положительности линейных форм» . Журнал компьютерных и системных наук . 6 (6): 639–650. DOI : 10.1016 / S0022-0000 (72) 80034-5 . ISSN 0022-0000 .

[4] Рейнгольд, Эдвард М. (1972-10-01). «Об оптимальности некоторых алгоритмов множества» . Журнал ACM . 19 (4): 649–659. DOI : 10.1145 / 321724.321730 . ISSN 0004-5411 . S2CID 18605212 .

[5] Препарата, Франко П. (1985). Вычислительная геометрия: введение . Шамос, Майкл Ян. Нью-Йорк: Springer-Verlag. ISBN 0-387-96131-3. OCLC 11970840 .

[6] Бен-Ор, Майкл (1983-12-01). «Нижние оценки для алгебраических вычислительных деревьев» . Материалы пятнадцатого ежегодного симпозиума ACM по теории вычислений . СТОК '83. Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники: 80–86. DOI : 10.1145 / 800061.808735 . ISBN 978-0-89791-099-6. S2CID 1499957 .

[7] Добкин, Дэвид; Липтон, Ричард Дж. (1976-06-01). «Многомерные поисковые задачи» . SIAM Journal on Computing . 5 (2): 181–186. DOI : 10.1137 / 0205015 . ISSN 0097-5397 .

[8] Майкл Стил, J; Яо, Эндрю К. (1982-03-01). «Нижние оценки для алгебраических деревьев решений» . Журнал алгоритмов . 3 (1): 1–8. DOI : 10.1016 / 0196-6774 (82) 90002-5 . ISSN 0196-6774 .

[Beals-9] Билс, Р .; Buhrman, H .; Умная.; Моска, М .; де Вольф, Р. (2001). «Квантовые оценки снизу по многочленам». Журнал ACM . 48 (4): 778–797. arXiv : квант-ph / 9802049 . DOI : 10.1145 / 502090.502097 . S2CID 1078168 .

[BlumImpagliazzo_1995-10] Блюм, М .; Impagliazzo, Р. (1987). «Общие оракулы и классы оракулов». Труды 18-го IEEE FOCS . С. 118–126.

[HartmanisHemachandra-11] Hartmanis, J .; Хемачандра, Л. (1987), «Односторонние функции, устойчивость и неизоморфизм NP-полных наборов», Технический отчет DCS TR86-796, Корнельский университет

[Tardos-12] Tardos, G. (1989). «Сложность запроса, или почему сложно отделить NP ^A ∩ coNP ^A от P ^A случайными оракулами A ?». Combinatorica . 9 (4): 385–392. DOI : 10.1007 / BF02125350 . S2CID 45372592 .

[Nisan-13] Нисан, Н. (1989). «ЭКИПАЖНЫЕ ПРОГРАММЫ и деревья решений». Материалы 21-го ACM STOC . С. 327–335.

[KT13-14] Кулькарни, Р. и Тал, А. О чувствительности к дробному блоку. Электронный коллоквиум по вычислительной сложности (ECCC). Vol. 20. 2013.

[ABBLSS17-15] Амбаинис, Андрис; Балодис, Каспарс; Беловс, Александр; Ли, Трой; Сантха, Миклош; Смотровы, Юрис (04.09.2017). «Разделение сложности запросов на основе функций указателя» . Журнал ACM . 64 (5): 32: 1–32: 24. arXiv : 1506.04719 . DOI : 10.1145 / 3106234 . ISSN 0004-5411 . S2CID 10214557 .

[ABKRT-16] Ааронсон, Скотт; Бен-Давид, Шалев; Котари, Робин; Рао, Шравас; Тал, Авишай (2020-10-23). «Степень против приблизительной степени и квантовые последствия теоремы Хуанга о чувствительности». arXiv : 2010.12629 [ квант-ф ].

[Midrijanis-17] Мидриджанис, Гатис (2004), «Точная квантовая сложность запроса для полных булевых функций», arXiv : Quant-ph / 0403168

[Midrijanis2-18] Мидриджанис, Гатис (2005), «О рандомизированных и квантовых сложностях запросов», arXiv : Quant-ph / 0501142

[NisanSzegedy-19] Нисан, Ноам; Сегеди, Марио (1992-07-01). «О степени булевых функций как вещественных многочленов» . Материалы двадцать четвертого ежегодного симпозиума ACM по теории вычислений . СТОК '92. Виктория, Британская Колумбия, Канада: Ассоциация вычислительной техники: 462–467. DOI : 10.1145 / 129712.129757 . ISBN 978-0-89791-511-3. S2CID 6919144 .

[Rub95-20] Рубинштейн, Дэвид (1995-06-01). «Чувствительность против блочной чувствительности булевых функций» . Combinatorica . 15 (2): 297–299. DOI : 10.1007 / BF01200762 . ISSN 1439-6912 . S2CID 41010711 .

[Huang-21] Хуан, Хао (2019). «Индуцированные подграфы гиперкубов и доказательство гипотезы о чувствительности». Анналы математики . 190 (3): 949–955. arXiv : 1907.00847 . DOI : 10.4007 / annals.2019.190.3.6 . ISSN 0003-486X . JSTOR 10.4007 / annals.2019.190.3.6 . S2CID 195767594 .

[22] Кларрайх, Эрика. «Гипотеза десятилетней давности компьютерных наук, решенная на двух страницах» . Журнал Quanta . Проверено 26 июля 2019 .

[HKP-23] Хатами, Пуйя; Кулкарни, Рагхав; Панкратов, Денис (22.06.2011). «Вариации гипотезы о чувствительности» . Теория вычислений . 1 : 1-27. DOI : 10.4086 / toc.gs.2011.004 . ISSN 1557-2862 . S2CID 6918061 .

[1]