Модель дерева рішень
У теорії складності обчислень та теорії складності комунікації модель дерева рішень являє собою модель обчислення або зв'язку, в якій алгоритм або процес комунікації вважаються, по суті, деревом рішень, тобто послідовністю операцій розгалуження на основі порівняння деяких величин, зіставленню присвоюється обчислювальна вартість одиниці.
Операції розгалуження називаються «тестами» або «запитами». У цьому параметрі даний алгоритм можна розглядати як обчислення булевої функції , де вхідний рядок запитів і висновок є остаточним рішенням. Кожен наступний запит залежить від попередніх.
Було запроваджено декілька варіантів моделей дерева рішень, в залежності від складності операцій, дозволених при обчисленні єдиного порівняння та способу розгалуження.
Моделі дерев рішень допомагають встановлювати нижні межі для обчислювальної складності для деяких класів обчислювальних задач та алгоритмів: нижня межа складності для найгірших випадків пропорційна найбільшій глибині серед дерев рішень для всіх можливих входів даної обчислювальної задачі. Обчислювальна складність задачі або алгоритму виражається в термінах моделі дерева рішень як «складність дерева рішень» або «складність запитів».
Класифікація обчислювальної складності за запитом
Просте дерево рішень
Модель, в якій кожне рішення базується на порівнянні двох чисел за постійний час, називається простою моделлю дерева рішень. Її було введено для встановлення обчислювальної складності сортування та пошуку.[1]
Найпростіша ілюстрація цієї методики нижньої межі полягає в задачі находження найменшого числа серед n чисел, використовуючи лише порівняння. У цьому випадку модель дерева рішень є бінарним деревом. Алгоритми цієї пошукової задачі можуть призвести до різних результатів n (оскільки будь-яке з n даних може виявитися найменшим). Відомо, що глибина бінарного дерева з n листів є що найменше , що дає нижню межу для пошукової задачі.
Проте ця нижня межа є слабкою, оскільки наступний простий аргумент показує, що необхідно виконати принаймні n - 1 порівняння: перш ніж можна визначити найменше число, кожен номер, крім найменшого, повинен «втратити» (порівняти більший) принаймні одне порівняння.[джерело?]
Таким же чином можна отримати оцінку нижньої межі для задачі сортування. У цьому випадку існування численних алгоритмів зіставлення-сортування, які мають таку ж складність часу, а саме сортування злиттям та пірамідальне сортування, показує, що ця межа є точною і не може бути покращена.
Лінійне дерево рішень
Лінійні дерева рішень, як і звичайні дерева рішень, складають рішення розгалуження на основі сукупності значень як вхідних даних. На відміну від бінарних дерев рішень, дерева лінійних рішень мають три вихідні гілки. Лінійна функція тестується і розгалуження приймаються на основі знаку функції (негативна, позитивна, або 0).
Геометрично, визначає гіперплощину в Rn. Набір вхідних значень, що досягають певних вузлів, являє собою перетин півплощин, визначених вузлами.
Алгебраїчне дерево рішень
Алгебраїчні дерева рішень — це узагальнення лінійних дерев рішень, щоб тестові функції були поліномами ступеня d. Геометрично простір поділяється на напів-алгебраїчні множини (узагальнення гіперплощини). Оцінка складності більш важка.
Класифікація обчислювальної моделі за запитом
Детерміноване дерево рішень
Якщо результат дерева рішень є , для всіх , дерево рішень вважається «обчислювальним» . Глибина дерева — це максимальна кількість запитів, які можуть траплятися до досягнення листа та отриманого результату., складність детермінованого дерева рішень є найменшою глибиною серед всіх детерміністичних дерев рішень, які обчислюють .
Рандомізоване дерево рішень
Один із способів визначення рандомізованого дерева рішень — додати до дерева додаткові вузли, кожен з яких контролюється імовірністю . Ще одне еквівалентне визначення полягає у виборі цілого дерева рішень на початку з набору дерев рішень на основі розподілу ймовірності. На основі цього другого визначення складність рандомізованого дерева визначається як найбільша глибина серед усіх дерев, пов'язаних з ймовірністю, більшою за 0. визначається як складність найнижчої глибини рандомізованого дерева рішень, результатом якого є з ймовірністю принаймні для всіх (тобто з обмеженою двосторонньою помилкою).
відома як рандомізована складність рішення алгоритму Монте-Карло, оскільки результат може бути невірним з обмеженою двосторонньою помилкою. Проблема складності рішень у алгоритмі Лас-Вегас вимірює очікувану глибину дерева рішень, яке має бути правильним (тобто має помилку нуля). Існує також одностороння версія обмеженої помилки, відома як .
Недетерміноване дерево рішень
Недетермінована складність рішення функції дерева найчастіше відома як складність цієї функції. Вона вимірює кількість вхідних бітів, які потрібно буде розглянути на недетермінованому алгоритмі, щоб оцінити функцію з упевненістю.
Квантове дерево рішень
Квантова складність дерева рішень — це глибина найменшої глибини квантового дерева рішень, що дає результат з вірогідністю щонайменше для всіх . Інша кількість визначається як глибина найменшої глибини квантового дерева рішень, що дає результат з вірогідністю 1 у всіх випадках (тобто точно обчислює ). і більш широко відомі як квантові запити складності, оскільки пряме визначення квантового дерева рішень є більш складним, ніж у класичному випадку. Подібно до рандомного випадку, ми визначаємо та .
Зв'язок між різними моделями
Відразу з визначень випливає, що для всіх -бітних булевих функцій , , and .
Блум і Імпагліаззо,[2] Гартманіс і Хемачандра,[3] та Тардо[4] самостійно виявили, що . Ноам Ніссан встановив, що комплексне розмаїття рішень рандомізованих дерев рішень Монте-Карло також пов'язане з детермінованою складністю дерева рішень: .[5]. (Ніссан також показав, що ). Найсильніші відносини між моделями Монте-Карло та Лас-Вегаса: .[6]. Це співвідношення оптимально до полігоритмічних факторів.[7]
Квантова складність дерева рішень також поліноміально пов'язана з . Мидріджаніс показав, що ,[8][9] поліпшення кварцового зв'язку, зумовлене Beals'ом[10] також показав, що досі найвідоміший зв'язок. Однак найбільший відомий розрив між детермінованими та квантовими ускладненнями запитів є лише квадратичним. Квадратичний розрив досягнуто для функції алгоритму Грувера; доки .
Важливо зазначити, що ці поліноміальні відносини справедливі лише для «повних» булевих функцій. Для часткових логічних функцій, які мають інтервальну підмножину , експоненціальне розділення між та можливо; перший приклад такої проблеми був виявлений Дойчем та Йожи.
Ці співвідношення можна підсумувати за такими нерівностями, які відповідають дійсним чинникам:[9]
Див. також
Посилання
- "Data structures and algorithms, by Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
- Blum, M.; Impagliazzo, R. (1987). Generic oracles and oracle classes. Proceedings of 18th IEEE FOCS. с. 118–126.
- Hartmanis, J.; Hemachandra, L. (1987). One-way functions, robustness, and non-isomorphism of NP-complete sets. Technical Report DCS TR86-796, Cornell University.
- Tardos, G. (1989). Query complexity, or why is it difficult to separate NPA ∩ coNPA from PA by random oracles A?. Combinatorica 9: 385–392. doi:10.1007/BF02125350.
- Nisan, N. (1989). CREW PRAMs and decision trees. Proceedings of 21st ACM STOC. с. 327–335.
- Kulkarni, R. and Tal, A. On Fractional Block Sensitivity. Electronic Colloquium on Computational Complexity (ECCC). Vol. 20. 2013.
- 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.
- Midrijanis, Gatis (2004). Exact quantum query complexity for total Boolean functions. arXiv:quant-ph/0403168. arXiv:quant-ph/0403168.
- Midrijanis, Gatis (2005). On randomized and quantum query complexities. arXiv:quant-ph/0501142. arXiv:quant-ph/0501142.
- Beals, R.; Buhrman, H.; Cleve, R.; Mosca, M.; de Wolf, R. (2001). Quantum lower bounds by polynomials. Journal of the ACM 48: 778–797.
- 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.
- S. Aaronson. Quantum Certificate Complexity. IEEE Conference on Computational Complexity, pp. 171—178, 2003.