Модель дерева решений
Модель вычислительной сложности

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

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

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

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

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

Деревья сравнения и нижние границы сортировки

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

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

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

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

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

Другие нижние границы дерева решений используют то, что запрос является сравнением. Например, рассмотрим задачу использования только сравнений для нахождения наименьшего числа среди чисел. Прежде чем наименьшее число может быть определено, каждое число, кроме наименьшего, должно «проиграть» (сравнить большее) по крайней мере в одном сравнении. Таким образом, требуется по крайней мере сравнений, чтобы найти минимум. (Информационно-теоретический аргумент здесь дает только нижнюю границу .) Похожий аргумент работает для общих нижних границ для вычисления порядковых статистик . [2] : 214  н {\displaystyle n} н − 1 {\displaystyle n-1} бревно ⁡ ( н ) {\displaystyle \log(n)}

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

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

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

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

Сложности булевых деревьев решений

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

Детерминированное дерево решений

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

Рандомизированное дерево решений

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

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

Недетерминированное дерево решений

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

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

Квантовое дерево решений

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

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

Билс и др. установили, что и . [9] Q 0 ( f ) ≥ deg ⁡ ( f ) / 2 {\displaystyle Q_{0}(f)\geq \deg(f)/2} Q 2 ( f ) ≥ deg ~ ( f ) / 2 {\displaystyle Q_{2}(f)\geq {\widetilde {\deg }}(f)/2}

Взаимосвязи между мерами сложности булевых функций

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

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

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

Предположение о чувствительности

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

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

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

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

Смотрите также

Ссылки

  1. ^ Форд, Лестер Р. младший; Джонсон, Селмер М. (1959-05-01). «Проблема турнира». The American Mathematical Monthly . 66 (5): 387– 389. doi :10.1080/00029890.1959.11989306. ISSN  0002-9890.
  2. ^ ab Введение в алгоритмы. Кормен, Томас Х. (Третье изд.). Кембридж, Массачусетс: MIT Press. 2009. ISBN 978-0-262-27083-0. OCLC  676697295.{{cite book}}: 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. ^ Preparata, Franco P. (1985). Computational geometry : an introduction. Шамос, Майкл Ян. Нью-Йорк: Springer-Verlag. ISBN 0-387-96131-3. OCLC  11970840.
  6. ^ Бен-Ор, Майкл (1983-12-01). "Нижние границы для деревьев алгебраических вычислений". Труды пятнадцатого ежегодного симпозиума ACM по теории вычислений - STOC '83 . Нью-Йорк, Нью-Йорк, США: Ассоциация вычислительной техники. стр.  80–86 . doi : 10.1145/800061.808735 . ISBN 978-0-89791-099-6. S2CID  1499957.
  7. ^ Добкин, Дэвид; Липтон, Ричард Дж. (1976-06-01). «Многомерные задачи поиска». Журнал SIAM по вычислениям . 5 (2): 181– 186. doi :10.1137/0205015. ISSN  0097-5397.
  8. ^ Майкл Стил, Дж.; Яо, Эндрю К. (1982-03-01). «Нижние границы для алгебраических деревьев решений». Журнал алгоритмов . 3 (1): 1– 8. doi :10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
  9. ^ ab Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). "Квантовые нижние границы с помощью полиномов". Journal of the ACM . 48 (4): 778– 797. arXiv : quant-ph/9802049 . doi :10.1145/502090.502097. S2CID  1078168.
  10. ^ Блум, М.; Импальяццо, Р. (1987). «Общие оракулы и классы оракулов». Труды 18-го IEEE FOCS . С.  118–126 .
  11. ^ Хартманис, Дж.; Хемачандра, Л. (1987), «Односторонние функции, надежность и неизоморфизм NP-полных множеств», Технический отчет DCS TR86-796, Корнельский университет
  12. ^ Тардос, Г. (1989). «Сложность запроса, или почему трудно отделить NP A  ∩  coNP A от P A случайными оракулами A ?». Combinatorica . 9 (4): 385– 392. doi :10.1007/BF02125350. S2CID  45372592.
  13. ^ ab Nisan, N. (1989). "CREW PRAMs и деревья решений". Труды 21-го ACM STOC . С.  327–335 .
  14. ^ Кулкарни, Р. и Тал, А. О дробной блочной чувствительности. Электронный коллоквиум по вычислительной сложности (ECCC). Том 20. 2013.
  15. ^ аб Амбайнис, Андрис; Балодис, Каспарс; Беловс, Александрс; Ли, Трой; Санта, Миклош; Смотровс, Юрис (04.09.2017). «Разделение сложности запроса на основе функций указателя». Журнал АКМ . 64 (5): 32:1–32:24. arXiv : 1506.04719 . дои : 10.1145/3106234. ISSN  0004-5411. S2CID  10214557.
  16. ^ Ааронсон, Скотт; Бен-Дэвид, Шалев; Котари, Робин; Рао, Шравас; Тал, Авишай (2020-10-23). ​​«Степень против приближенной степени и квантовые следствия теоремы Хуанга о чувствительности». arXiv : 2010.12629 [quant-ph].
  17. ^ Мидрианис, Гатис (2004), «Точная квантовая сложность запроса для полных булевых функций», arXiv : quant-ph/0403168
  18. ^ Мидрианис, Гатис (2005), «О сложностях рандомизированных и квантовых запросов», arXiv : quant-ph/0501142
  19. ^ Хуан, Хао (2019). «Индуцированные подграфы гиперкубов и доказательство гипотезы о чувствительности». Annals of Mathematics . 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.
  20. ^ Кларрайх, Эрика (25 июля 2019 г.). «Десятилетняя гипотеза компьютерной науки решена на двух страницах». Журнал Quanta . Получено 26 июля 2019 г.

Опросы

  • Бурман, Гарри; де Вольф, Рональд (2002), «Меры сложности и сложность дерева решений: обзор» (PDF) , Теоретическая информатика , 288 (1): 21– 43, doi : 10.1016/S0304-3975(01)00144-X
Retrieved from "https://en.wikipedia.org/w/index.php?title=Decision_tree_model&oldid=1257253087"