Модель дерева рішень

У теорії складності обчислень та теорії складності комунікації^[en] модель дерева рішень являє собою модель обчислення або зв'язку, в якій алгоритм або процес комунікації вважаються, по суті, деревом рішень, тобто послідовністю операцій розгалуження на основі порівняння деяких величин, зіставленню присвоюється обчислювальна вартість одиниці.

Операції розгалуження називаються «тестами» або «запитами». У цьому параметрі даний алгоритм можна розглядати як обчислення булевої функції ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$, де вхідний рядок запитів і висновок є остаточним рішенням. Кожен наступний запит залежить від попередніх.

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

Моделі дерев рішень допомагають встановлювати нижні межі для обчислювальної складності для деяких класів обчислювальних задач та алгоритмів: нижня межа складності для найгірших випадків^[en] пропорційна найбільшій глибині серед дерев рішень для всіх можливих входів даної обчислювальної задачі. Обчислювальна складність задачі або алгоритму виражається в термінах моделі дерева рішень як «складність дерева рішень» або «складність запитів».

Класифікація обчислювальної складності за запитом[ред. | ред. код]

Просте дерево рішень[ред. | ред. код]

Модель, в якій кожне рішення базується на порівнянні двох чисел за постійний час, називається простою моделлю дерева рішень. Її було введено для встановлення обчислювальної складності сортування^[en] та пошуку.^[1]

Найпростіша ілюстрація цієї методики нижньої межі полягає в задачі находження найменшого числа серед n чисел, використовуючи лише порівняння. У цьому випадку модель дерева рішень є бінарним деревом. Алгоритми цієї пошукової задачі можуть призвести до різних результатів n (оскільки будь-яке з n даних може виявитися найменшим). Відомо, що глибина бінарного дерева з n листів є що найменше ${\displaystyle \log n}$, що дає нижню межу ${\displaystyle \Omega (\log n)}$ для пошукової задачі.

Проте ця нижня межа є слабкою, оскільки наступний простий аргумент показує, що необхідно виконати принаймні n - 1 порівняння: перш ніж можна визначити найменше число, кожен номер, крім найменшого, повинен «втратити» (порівняти більший) принаймні одне порівняння.^{[джерело?]}

Таким же чином можна отримати оцінку нижньої межі ${\displaystyle \Omega (n\log n)}$ для задачі сортування^[en]. У цьому випадку існування численних алгоритмів зіставлення-сортування, які мають таку ж складність часу, а саме сортування злиттям та пірамідальне сортування, показує, що ця межа є точною і не може бути покращена.

Лінійне дерево рішень[ред. | ред. код]

Лінійні дерева рішень, як і звичайні дерева рішень, складають рішення розгалуження на основі сукупності значень як вхідних даних. На відміну від бінарних дерев рішень, дерева лінійних рішень мають три вихідні гілки. Лінійна функція ${\displaystyle f(x_{1},\dots ,x_{i})}$ тестується і розгалуження приймаються на основі знаку функції (негативна, позитивна, або 0).

Геометрично, ${\displaystyle f(x)}$ визначає гіперплощину в Rⁿ. Набір вхідних значень, що досягають певних вузлів, являє собою перетин півплощин, визначених вузлами.

Алгебраїчне дерево рішень[ред. | ред. код]

Алгебраїчні дерева рішень — це узагальнення лінійних дерев рішень, щоб тестові функції були поліномами ступеня d. Геометрично простір поділяється на напів-алгебраїчні множини (узагальнення гіперплощини). Оцінка складності більш важка.

Класифікація обчислювальної моделі за запитом[ред. | ред. код]

Детерміноване дерево рішень[ред. | ред. код]

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

Рандомізоване дерево рішень[ред. | ред. код]

Один із способів визначення рандомізованого дерева рішень — додати до дерева додаткові вузли, кожен з яких контролюється імовірністю ${\displaystyle p_{i}}$. Ще одне еквівалентне визначення полягає у виборі цілого дерева рішень на початку з набору дерев рішень на основі розподілу ймовірності. На основі цього другого визначення складність рандомізованого дерева визначається як найбільша глибина серед усіх дерев, пов'язаних з ймовірністю, більшою за 0. ${\displaystyle R_{2}(f)}$ визначається як складність найнижчої глибини рандомізованого дерева рішень, результатом якого є ${\displaystyle f(x)}$ з ймовірністю принаймні ${\displaystyle 2/3}$ для всіх ${\displaystyle x\in \{0,1\}^{n}}$ (тобто з обмеженою двосторонньою помилкою).

${\displaystyle R_{2}(f)}$ відома як рандомізована складність рішення алгоритму Монте-Карло, оскільки результат може бути невірним з обмеженою двосторонньою помилкою. Проблема складності рішень у алгоритмі Лас-Вегас ${\displaystyle R_{0}(f)}$ вимірює очікувану глибину дерева рішень, яке має бути правильним (тобто має помилку нуля). Існує також одностороння версія обмеженої помилки, відома як ${\displaystyle R_{1}(f)}$.

Недетерміноване дерево рішень[ред. | ред. код]

Недетермінована складність рішення функції дерева найчастіше відома як складність цієї функції. Вона вимірює кількість вхідних бітів, які потрібно буде розглянути на недетермінованому алгоритмі, щоб оцінити функцію з упевненістю.

Квантове дерево рішень[ред. | ред. код]

Квантова складність дерева рішень ${\displaystyle Q_{2}(f)}$ — це глибина найменшої глибини квантового дерева рішень, що дає результат ${\displaystyle f(x)}$ з імовірністю щонайменше ${\displaystyle 2/3}$ для всіх ${\displaystyle x\in \{0,1\}^{n}}$. Інша кількість ${\displaystyle Q_{E}(f)}$ визначається як глибина найменшої глибини квантового дерева рішень, що дає результат ${\displaystyle f(x)}$ з імовірністю 1 у всіх випадках (тобто точно обчислює ${\displaystyle f}$). ${\displaystyle Q_{2}(f)}$ і ${\displaystyle Q_{E}(f)}$ більш широко відомі як квантові запити складності, оскільки пряме визначення квантового дерева рішень є більш складним, ніж у класичному випадку. Подібно до рандомного випадку, ми визначаємо ${\displaystyle Q_{0}(f)}$ та ${\displaystyle Q_{1}(f)}$.

Зв'язок між різними моделями[ред. | ред. код]

Відразу з визначень випливає, що для всіх ${\displaystyle n}$-бітних булевих функцій ${\displaystyle f}$, ${\displaystyle Q_{2}(f)\leq R_{2}(f)\leq R_{1}(f)\leq R_{0}(f)\leq D(f)\leq n}$, and ${\displaystyle Q_{2}(f)\leq Q_{E}(f)\leq D(f)\leq n}$.

Блум і Імпагліаззо,^[2] Гартманіс і Хемачандра,^[3] та Тардо^[4] самостійно виявили, що ${\displaystyle D(f)\leq R_{0}(f)^{2}}$. Ноам Ніссан^[en] встановив, що комплексне розмаїття рішень рандомізованих дерев рішень Монте-Карло також пов'язане з детермінованою складністю дерева рішень: ${\displaystyle D(f)=O(R_{2}(f)^{3})}$.^[5]. (Ніссан також показав, що ${\displaystyle D(f)=O(R_{1}(f)^{2})}$). Найсильніші відносини між моделями Монте-Карло та Лас-Вегаса: ${\displaystyle R_{0}(f)=O(R_{2}(f)^{2}\log R_{2}(f))}$.^[6]. Це співвідношення оптимально до полігоритмічних факторів.^[7]

Квантова складність дерева рішень ${\displaystyle Q_{2}(f)}$ також поліноміально пов'язана з ${\displaystyle D(f)}$. Мидріджаніс показав, що ${\displaystyle D(f)=O(Q_{E}(f)^{3})}$,^[8][9] поліпшення кварцового зв'язку, зумовлене Beals'ом^[10] також показав, що ${\displaystyle D(f)=O(Q_{2}(f)^{6})}$ досі найвідоміший зв'язок. Однак найбільший відомий розрив між детермінованими та квантовими ускладненнями запитів є лише квадратичним. Квадратичний розрив досягнуто для функції алгоритму Грувера; ${\displaystyle D(OR_{n})=n}$ доки ${\displaystyle Q_{2}(OR_{n})=\Theta ({\sqrt {n}})}$.

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

Ці співвідношення можна підсумувати за такими нерівностями, які відповідають дійсним чинникам:^[9]

• ${\displaystyle D(f)\leq R_{0}(f)^{2}}$^[2][3][4]
• ${\displaystyle D(f)\leq R_{1}(f)R_{2}(f)}$^[5]
• ${\displaystyle D(f)\leq R_{2}(f)^{3}}$^[5]
• ${\displaystyle R_{0}(f)\leq R_{2}(f)^{2}\log R_{2}(f)}$^[6]
• ${\displaystyle D(f)\leq Q_{2}(f)^{6}}$^[10]
• ${\displaystyle D(f)\leq Q_{E}(f)^{2}Q_{2}(f)^{2}}$^[10]
• ${\displaystyle D(f)\leq Q_{1}(f)^{2}Q_{2}(f)^{2}}$^[11]
• ${\displaystyle R_{0}(f)\leq Q_{1}(f)Q_{2}(f)^{2}\log N}$^[12]
• ${\displaystyle D(f)\leq Q_{1}(f)Q_{2}(f)^{2}}$^[9]

Див. також[ред. | ред. код]

• Мінімальне кістякове дерево

Посилання[ред. | ред. код]