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

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

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

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

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

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

границы сортировки

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

Например, многие алгоритмы сортировки являются сортировками сравнения , что означает, что они получают информацию только о входной последовательности. $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}$, переупорядочивает входную последовательность.)

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

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

Другие нижние границы дерева решений основаны на том, что запрос представляет собой сравнение. Например, рассмотрим задачу использования только сравнений для нахождения наименьшего числа среди $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$. Геометрически пространство разделено на полуалгебраические множества (обобщение гиперплоскости).

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

логического

Для логических деревьев решений задача состоит в том, чтобы вычислить значение n-битной логической функции. $f:\{0,1\}^{n}\to \{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)$.

решений

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

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

Квантовое

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

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

Билс и др. установил, что $Q_{0}(f)\geq \deg(f)/2$ и $Q_{2}(f)\geq {\widetilde {\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$. Поиск наилучших верхних границ в обратном направлении является основной целью в области сложности запросов.

Все эти типы сложности запросов связаны полиномиально. Блюм и Импальяццо, Хартманис и Хемачандра, и Тардос независимо обнаружил, что $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})$, и эта граница точная. Мидрианис показал, что $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)$, поэтому гипотеза конкретно касается поиска нижней границы чувствительности. Поскольку все ранее обсуждавшиеся меры сложности связаны полиномиально, точный тип меры сложности не имеет значения. Однако обычно это формулируется как вопрос о связи чувствительности с чувствительностью блока.

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

В 2019 году Хао Хуан доказал гипотезу чувствительности, показав, что $bs(f)=O(s(f)^{4})$.

См. также

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

Ссылки

Опросы

• Бурман, Гарри; де Вольф, Рональд (2002), «Меры сложности и сложность дерева решений: обзор» (PDF) , Theoretical Computer Science , 288 (1): 21–43, doi : 10.1016/S0304-3975(01)00144-X