В вычислительной сложности модель дерева решений является модель вычислений , в которой алгоритм считается в основном дерево решений , то есть последовательность запросов или тестов , которые сделаны адаптивно, поэтому результаты предыдущих тестов могут повлиять на тест исполняется далее.
Как правило, эти тесты имеют небольшое количество результатов (например, вопрос типа да-нет) и могут быть выполнены быстро (скажем, с единичными вычислительными затратами), поэтому наихудшая временная сложность алгоритма в модели дерева решений соответствует глубина соответствующего дерева решений. Это понятие вычислительной сложности проблемы или алгоритма в модели дерева решений называется сложностью его дерева решений или сложностью запроса .
Решение дерева модель играет важная роль в установлении нижних оценок для теории сложности для некоторых классов вычислительных задач и алгоритмов. Было введено несколько вариантов моделей дерева решений, в зависимости от вычислительной модели и типа алгоритмов запросов, которые разрешено выполнять.
Например, дерево решений аргумент используется , чтобы показать , что сравнение сортировать по предметы должны взять сравнения. Для сортировки сравнения запрос представляет собой сравнение двух элементов., с двумя исходами (при условии, что никакие элементы не равны): либо или же . Сортировки сравнения могут быть выражены в виде дерева решений в этой модели, поскольку такие алгоритмы сортировки выполняют только эти типы запросов.
Деревья сравнения и нижние границы для сортировки
Деревья решений часто используются для понимания алгоритмов сортировки и других подобных проблем; это было впервые сделано Фордом и Джонсоном. [1]
Например, многие алгоритмы сортировки являются сортировками сравнения , что означает, что они получают информацию только о входной последовательности. с помощью локальных сравнений: проверка того, , , или же . Если предположить, что все элементы, которые нужно отсортировать, различны и сопоставимы, это можно перефразировать как вопрос типа «да» или «нет»: is?
Эти алгоритмы могут быть смоделированы как двоичные деревья решений, где запросы являются сравнениями: внутренний узел соответствует запросу, а дочерние узлы соответствуют следующему запросу, когда ответ на вопрос - да или нет. Для листовых узлов вывод соответствует перестановке это описывает, как входная последовательность была зашифрована из полностью упорядоченного списка элементов. (Обратная перестановка,, меняет порядок входной последовательности.)
Можно показать, что сортировки сравнения должны использовать сравнений с помощью простого аргумента: чтобы алгоритм был правильным, он должен уметь выводить все возможные перестановки элементы; в противном случае алгоритм не сможет использовать эту конкретную перестановку в качестве входных данных. Итак, соответствующее дерево решений должно иметь как минимум столько же листьев, сколько перестановок:листья. Любое двоичное дерево с как минимум листья имеют глубину не менее , так что это нижняя граница времени выполнения алгоритма сортировки сравнения. В этом случае существование множества алгоритмов сравнения-сортировки, имеющих такую временную сложность, таких как сортировка слиянием и heapsort , демонстрирует, что граница жесткая. [2] : 91
В этом аргументе ничего не говорится о типе запроса, поэтому он фактически доказывает нижнюю границу для любого алгоритма сортировки, который можно смоделировать как двоичное дерево решений. По сути, это переформулировка теоретико-информационного аргумента о том, что правильный алгоритм сортировки должен изучать как минимумбиты информации о входной последовательности. В результате это также работает и для рандомизированных деревьев решений.
В других нижних границах дерева решений используется то, что запрос является сравнением. Например, рассмотрим задачу использования только сравнений, чтобы найти наименьшее число средичисла. Прежде чем можно будет определить наименьшее число, каждое число, кроме наименьшего, должно «проиграть» (сравнить большее) хотя бы в одном сравнении. Итак, требуется как минимумсравнения, чтобы найти минимум. (Теоретико-информационные аргументы здесь дают только нижнюю оценку.) Аналогичное рассуждение работает для общих нижних оценок для вычисления порядковой статистики . [2] : 214
Линейные и алгебраические деревья решений
Линейные деревья решений обобщают приведенные выше деревья решений сравнения на вычислительные функции, которые принимают действительные векторы. как вход. Тесты в линейных деревьях решений являются линейными функциями: для конкретного выбора действительных чисел, выведите знак . (Алгоритмы в этой модели могут зависеть только от знака вывода.) Деревья сравнения - это линейные деревья решений, потому что сравнение между а также соответствует линейной функции . Согласно своему определению, линейные деревья решений могут указывать только функциислои которого могут быть построены путем объединения и пересечения полупространств.
Алгебраические деревья решений являются обобщением линейных деревьев решений, которые позволяют тестовым функциям быть полиномами степени. Геометрически пространство разделено на полуалгебраические множества (обобщение гиперплоскости).
Эти модели деревьев решений, определенные Рабином [3] и Рейнгольдом [4] , часто используются для доказательства нижних оценок в вычислительной геометрии . [5] Например, Бен-Ор показал, что уникальность элемента (задача вычисления, где равен 0 тогда и только тогда, когда существуют различные координаты такой, что ) требует алгебраического дерева решений глубины . [6] Это было впервые показано для моделей линейных решений Добкиным и Липтоном. [7] Они также показываютнижняя оценка линейных деревьев решений для задачи о ранце, обобщенная Стилом и Яо на алгебраические деревья решений. [8]
Сложности логического дерева решений
Для булевых деревьев решений задача состоит в том, чтобы вычислить значение n-битной логической функции. для входа . Запросы соответствуют чтению бита ввода,, а на выходе . Каждый запрос может зависеть от предыдущих запросов. Существует много типов вычислительных моделей, использующих деревья решений, которые можно рассматривать, допуская несколько понятий сложности, называемых мерами сложности .
Детерминированное дерево решений
Если на выходе дерева решений , для всех , говорят, что дерево решений "вычисляет" . Глубина дерева - это максимальное количество запросов, которое может произойти до того, как будет достигнут лист и получен результат., сложность детерминированного дерева решений это наименьшая глубина среди всех детерминированных деревьев решений, которые вычисляют .
Рандомизированное дерево решений
Один из способов определить рандомизированное дерево решений - добавить в дерево дополнительные узлы, каждый из которых управляется вероятностью. Другое эквивалентное определение - определить его как распределение по детерминированным деревьям решений. На основе этого второго определения сложность рандомизированного дерева определяется как наибольшая глубина среди всех деревьев, поддерживающих базовое распределение. определяется как сложность рандомизированного дерева решений с наименьшей глубиной, результатом которого является с вероятностью не менее для всех (т.е. с ограниченной двусторонней ошибкой).
известна как сложность рандомизированного дерева решений Монте-Карло , потому что результат может быть неверным с ограниченной двусторонней ошибкой. Лас - Вегас сложность принятия дереваизмеряет ожидаемую глубину дерева решений, которое должно быть правильным (т. е. иметь нулевую ошибку). Существует также версия с односторонней ограниченной ошибкой, которая обозначается как.
Недетерминированное дерево решений
Недетерминированная сложность дерева решений функции чаще известна как сложность сертификата этой функции. Он измеряет количество входных битов, которые недетерминированный алгоритм должен будет просмотреть, чтобы точно оценить функцию.
Формально сложность сертификата в это размер наименьшего подмножества индексов такое, что для всех , если для всех , тогда . Сложность сертификата максимальная сложность сертификата по всем . Аналогичное понятие, в котором требуется, чтобы проверяющий был прав с вероятностью 2/3, обозначается.
Квантовое дерево решений
Сложность квантового дерева решений - это глубина квантового дерева решений с наименьшей глубиной, которое дает результат с вероятностью не менее для всех . Другое количество,, определяется как глубина квантового дерева решений с наименьшей глубиной, которое дает результат с вероятностью 1 во всех случаях (т.е. вычисляет точно). а также более известны как сложность квантовых запросов , потому что прямое определение дерева квантовых решений сложнее, чем в классическом случае. Как и в рандомизированном случае, мы определяем а также .
Эти понятия обычно ограничиваются понятиями степени и приблизительной степени. Степени из, обозначенный , является наименьшей степенью любого многочлена удовлетворение для всех . Приблизительная степень из, обозначенный , является наименьшей степенью любого многочлена удовлетворение в любое время а также в любое время .
Beals et al. установил, что а также . [9]
Связь между мерами сложности булевых функций
Непосредственно из определений следует, что для всех -битовые логические функции ,, а также . Поиск лучших верхних границ в обратном направлении - основная цель в области сложности запросов.
Все эти типы сложности запроса полиномиально связаны. Блюм и Импальяццо [10], Хартманис и Хемачандра [11] и Тардос [12] независимо друг от друга обнаружили, что. Ноам Нисан обнаружил, что сложность рандомизированного дерева решений Монте-Карло также полиномиально связана со сложностью детерминированного дерева решений:. [13] (Нисан также показал, что.) Более тесные отношения известны между моделями из Монте-Карло и Лас-Вегаса: . [14] Это соотношение оптимально с точностью до полилогарифмических факторов. [15] Что касается сложностей квантового дерева решений,, и эта граница жесткая. [16] [15] Мидриджанис показал, что, [17] [18] улучшение оценки четвертой степени из-за Билса и др. [9]
Важно отметить, что эти полиномиальные отношения действительны только для полных булевых функций. Для частичных булевых функций , у которых есть область подмножества, экспоненциальное разделение между а также возможно; первый пример такой проблемы был обнаружен Дойчем и Йозой .
Гипотеза о чувствительности
Для логической функции , То чувствительность в определяется как максимальная чувствительность общий , где чувствительность в это количество однобитовых изменений в которые меняют значение . Чувствительность связана с понятием совокупного влияния анализа булевых функций , которое равно средней чувствительности по всем параметрам..
Гипотеза о чувствительности - это гипотеза о том, что чувствительность полиномиально связана со сложностью запроса; то есть существует показатель степени такое, что для всех , а также . С помощью простого аргумента можно показать, что, поэтому гипотеза конкретно касается нахождения нижней границы чувствительности. Поскольку все ранее обсуждавшиеся меры сложности полиномиально связаны, точный тип меры сложности не имеет значения. Однако это обычно формулируется как вопрос о связи чувствительности с чувствительностью к блоку.
Блок чувствительности из, обозначенный , определяется как максимальная блочная чувствительность общий . Чувствительность блока в это максимальное количество непересекающихся подмножеств такой, что для любого из подмножеств , переворачивая кусочки соответствующий меняет значение . [13]
Поскольку чувствительность блока принимает максимум при большем выборе подмножеств, . Кроме того, чувствительность к блокам полиномиально связана с ранее обсужденными мерами сложности; например, статья Нисана о чувствительности к блокам показала, что. [13] Итак, можно перефразировать гипотезу о чувствительности, показав, что для некоторых, . В 1992 году Нисан и Сегеди предположили, чтодостаточно. [19] Это было бы сложно, поскольку Рубинштейн в 1995 году показал квадратичное разделение между чувствительностью и чувствительностью к блоку. [20]
В июле 2019 года, через 27 лет после первоначального высказывания гипотезы, Хао Хуан из Университета Эмори доказал гипотезу о чувствительности, показав, что. [21] Это доказательство особенно лаконично, доказывая это утверждение на двух страницах, когда предыдущий прогресс в отношении гипотезы о чувствительности был ограничен. [22] [23]
Резюме известных результатов
2 | 2, 3 | 2 | 2, 3 | 2, 3 | 3, 6 | 2, 3 | 2, 3 | 4 | 4 | ||
1 | 2 | 2 | 2, 3 | 2, 3 | 3, 6 | 2, 3 | 2, 3 | 3, 4 | 4 | ||
1 | 1 | 2 | 2, 3 | 2, 3 | 3, 6 | 1,5, 3 | 2, 3 | 3, 4 | 4 | ||
1 | 1 | 1, 2 | 2 | 2 | 2,22, 5 | 1,15, 3 | 1,63, 3 | 2, 4 | 2, 4 | ||
1 | 1 | 1 | 1 | 1,5, 2 | 2, 4 | 1,15, 2 | 1,63, 2 | 2 | 2 | ||
1 | 1 | 1 | 1 | 1 | 2, 4 | 1,15, 2 | 1,63, 2 | 2 | 2 | ||
1 | 1 | 1 | 1 | 1 | 1 | 1,15, 2 | 1,63, 2 | 2 | 2 | ||
1 | 1,33, 2 | 1,33, 3 | 2 | 2, 3 | 2, 3 | 3, 6 | 2, 3 | 2, 4 | 4 | ||
1 | 1,33, 2 | 1,33, 2 | 2 | 2 | 2 | 2 | 1 | 2 | 2 | ||
1 | 1 | 1 | 2 | 2, 3 | 2, 3 | 3, 6 | 1 | 2, 3 | 4 | ||
1 | 1 | 1 | 2 | 2 | 2 | 2 | 1 | 1 | 1 |
В этой таблице приведены результаты по разделению мер сложности булевых функций. Меры сложности: детерминированный, рандомизированный с нулевой ошибкой, рандомизированный с двусторонней ошибкой, сертификат, рандомизированный сертификат, чувствительность блока, чувствительность, точное количество, степень, квант и приблизительная степень сложности.
Число в -й ряд и -й столбец обозначает границы экспоненты , который является точной гранью всех удовлетворение для всех логических функций . Например, запись в строке D и столбце s - «3, 6», поэтому для всех , и существует функция такой, что .
Смотрите также
- Сравнительная сортировка
- Древо решений
- Гипотеза Андераа – Карпа – Розенберга
- Минимальное остовное дерево # Деревья решений
Рекомендации
- ^ Младший, Лестер Р. Форд; Джонсон, Селмер М. (1959-05-01). «Турнирная задача» . Американский математический ежемесячник . 66 (5): 387–389. DOI : 10.1080 / 00029890.1959.11989306 . ISSN 0002-9890 .
- ^ а б Введение в алгоритмы . Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. ISBN. 978-0-262-27083-0. OCLC 676697295 .CS1 maint: другие ( ссылка )
- ^ Рабин, Майкл О. (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 .
- ^ Майкл Стил, Дж; Яо, Эндрю К. (1982-03-01). «Нижние оценки для алгебраических деревьев решений» . Журнал алгоритмов . 3 (1): 1–8. DOI : 10.1016 / 0196-6774 (82) 90002-5 . ISSN 0196-6774 .
- ^ а б Beals, R .; 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, Корнельский университет
- ^ Тардос, Г. (1989). «Сложность запроса, или почему сложно отделить NP A ∩ coNP A от P A случайными оракулами A ?». Combinatorica . 9 (4): 385–392. DOI : 10.1007 / BF02125350 . S2CID 45372592 .
- ^ а б в Нисан, Н. (1989). «ЭКИПАЖНЫЕ ПРОГРАММЫ и деревья решений». Материалы 21-го ACM STOC . С. 327–335.
- ^ Кулькарни, Р. и Тал, А. О чувствительности к дробному блоку. Электронный коллоквиум по вычислительной сложности (ECCC). Vol. 20. 2013.
- ^ а б Амбаинис, Андрис; Балодис, Каспарс; Беловс, Александр; Ли, Трой; Сантха, Миклош; Смотровы, Юрис (04.09.2017). «Разделение сложности запросов на основе функций указателя» . Журнал ACM . 64 (5): 32: 1–32: 24. arXiv : 1506.04719 . DOI : 10.1145 / 3106234 . ISSN 0004-5411 . S2CID 10214557 .
- ^ а б Ааронсон, Скотт; Бен-Давид, Шалев; Котари, Робин; Рао, Шравас; Тал, Авишай (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