Модель у вигляді дерева рішень

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

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

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

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

Класифікація обчислювальної складності за запитом

Просте дерево рішень

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

Найпростіша ілюстрація цієї методики нижньої межі полягає в задачі находження найменшого числа серед 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}$.

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

Квантова складність дерева рішень ${\displaystyle Q_{2}(f)}$ також поліноміально пов'язана з ${\displaystyle D(f)}$. Мидріджаніс показав, що ${\displaystyle D(f)=O(Q_{E}(f)^{3})}$, поліпшення кварцового зв'язку, зумовлене Beals'ом також показав, що ${\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)}$ можливо; перший приклад такої проблеми був виявлений Дойчем та Йожи.

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

• ${\displaystyle D(f)\leq R_{0}(f)^{2}}$
• ${\displaystyle D(f)\leq R_{1}(f)R_{2}(f)}$
• ${\displaystyle D(f)\leq R_{2}(f)^{3}}$
• ${\displaystyle R_{0}(f)\leq R_{2}(f)^{2}\log R_{2}(f)}$
• ${\displaystyle D(f)\leq Q_{2}(f)^{6}}$
• ${\displaystyle D(f)\leq Q_{E}(f)^{2}Q_{2}(f)^{2}}$
• ${\displaystyle D(f)\leq Q_{1}(f)^{2}Q_{2}(f)^{2}}$
• ${\displaystyle R_{0}(f)\leq Q_{1}(f)Q_{2}(f)^{2}\log N}$
• ${\displaystyle D(f)\leq Q_{1}(f)Q_{2}(f)^{2}}$

Див. також

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

Посилання

1. "Data structures and algorithms, by Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
2. Blum, M.; Impagliazzo, R. (1987). Generic oracles and oracle classes. Proceedings of 18th IEEE FOCS. с. 118—126.
3. Hartmanis, J.; Hemachandra, L. (1987), One-way functions, robustness, and non-isomorphism of NP-complete sets, Technical Report DCS TR86-796, Cornell University
4. Tardos, G. (1989). Query complexity, or why is it difficult to separate NP^A ∩ coNP^A from P^A by random oracles A?. Combinatorica. 9: 385—392. doi:10.1007/BF02125350.
5. (1989). CREW PRAMs and decision trees. Proceedings of 21st ACM STOC. с. 327—335.
6. Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.
7. Ambainis, A., Balodis, K., Belovs, A., Lee, T., Santha, M., and Smotrovs, J. (2015). Separations in query complexity based on pointer functions. arXiv preprint arXiv:1506.04719.
8. Midrijanis, Gatis (2004), Exact quantum query complexity for total Boolean functions, arXiv:quant-ph/0403168, arXiv:quant-ph/0403168
9. Midrijanis, Gatis (2005), On randomized and quantum query complexities, arXiv:quant-ph/0501142, arXiv:quant-ph/0501142
10. Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). Quantum lower bounds by polynomials. Journal of the ACM. 48: 778—797.
11. H. Buhrman, R. Cleve, R. de Wolf, and Ch. Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms. In 40th IEEE Symposium on Foundations of Computer Science (FOCS'99), pp.358-368. cs.CC/9904019, 1999.
12. S. Aaronson. Quantum Certificate Complexity. IEEE Conference on Computational Complexity, pp. 171—178, 2003.