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

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

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

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

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

Например, аргумент дерева решений используется, чтобы показать, что сравнения метод $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