Проблема различимости элементов

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

Это хорошо изученная проблема во многих различных моделях вычислений. Проблему можно решить, отсортировав список и проверив, есть ли последовательные равные элементы; его также можно решить за линейное ожидаемое время с помощью рандомизированного алгоритма , который вставляет каждый элемент в хеш-таблицу и сравнивает только те элементы, которые помещены в одну и ту же ячейку хеш-таблицы. ^[1]

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

Сложность дерева решений

Количество сравнений, необходимое для решения проблемы размера $n$ , в модели вычислений на основе сравнения, такой как дерево решений или алгебраическое дерево решений , $\Theta (n\log n)$ . Здесь, $\Theta$ использует большую тэта-нотацию , что означает, что проблема может быть решена за число сравнений, пропорциональное $n\log n$ ( линейная функция ) и что все решения требуют такого количества сравнений. ^[2] В этих моделях вычислений входные числа не могут использоваться для индексации памяти компьютера (как в решении хеш-таблицы), но доступны только путем вычисления и сравнения простых алгебраических функций их значений. Для этих моделей алгоритм, основанный на сортировке сравнения, решает проблему с точностью до постоянного коэффициента наилучшего возможного числа сравнений. Та же нижняя граница применима и к ожидаемому количеству сравнений в модели рандомизированного алгебраического дерева решений . ^[3]^[4]

Реальная сложность оперативной памяти

Если элементами в задаче являются действительные числа , нижняя граница дерева решений распространяется на реальную модель машины с произвольным доступом с набором команд, который включает в себя сложение, вычитание и умножение действительных чисел, а также сравнение и деление или получение остатка ( "пол"). ^[5] Отсюда следует, что сложность задачи в этой модели также $\Theta (n\log n)$ . Эта модель RAM охватывает больше алгоритмов, чем модель алгебраического дерева решений, поскольку она включает алгоритмы, использующие индексацию в таблицах. Однако в этой модели учитываются все шаги программы, а не только решения.

Сложность машины Тьюринга

Одноленточная детерминированная машина Тьюринга может решить задачу для n элементов по $m \geq log n$ бит каждый за время $O (n 2 м (м +2-log n))$ ,в то время как на недетерминированной машине временная сложность равна $O (nm (n + log m))$ . ^[6]

Квантовая сложность

Квантовые алгоритмы могут решить эту проблему быстрее, в ${\textstyle \Theta (n^{2/3})}$ запросы. Оптимальный алгоритм — Андрис Амбайнис . ^[7] Яоюнь Ши впервые доказал точную нижнюю границу, когда размер диапазона достаточно велик. ^[8] Амбайнис ^[9] и Кутин ^[10] независимо (и посредством различных доказательств) расширил свою работу, чтобы получить нижнюю оценку для всех функций.

Обобщение: поиск повторяющихся элементов

Элементы, встречающиеся более чем $n/k$ раз в мультинаборе размера $n$ может быть найден с помощью алгоритма, основанного на сравнении, алгоритма сильных нападающих Мисры-Гриса , за время $O(n\log k)$ . Проблема различимости элементов является частным случаем этой проблемы, когда $k=n$ . Это время является оптимальным в рамках модели вычислений в виде дерева решений . ^[11]

См. также

Проблема столкновения

Ссылки

^ Гил, Дж.; Мейер ауф дер Хайде, Ф.; Вигдерсон, А. (1990), «Не все ключи можно хешировать за постоянное время», Proc. 22-й симпозиум ACM по теории вычислений , стр. 244–253, doi : 10.1145/100216.100247 , S2CID 11943779 .
^ Бен-Ор, Майкл (1983), «Нижние оценки для деревьев алгебраических вычислений», Proc. 15-й симпозиум ACM по теории вычислений , стр. 80–86, doi : 10.1145/800061.808735 .
^ Григорьев Дима ; Карпински, Марек ; Хайде, Фридхельм Мейер; Смоленский, Роман (1996), «Нижняя оценка для рандомизированных алгебраических деревьев решений», Computational Complexity , 6 (4):357, doi : 10.1007/BF01270387 , S2CID 1462184 .
^ Григорьев, Дима (1999), «Нижние границы сложности для рандомизированных деревьев вычислений над полями с нулевой характеристикой», Computational Complexity , 8 (4): 316–329, doi : 10.1007/s000370050002 , S2CID 10641238 .
^ Бен-Амрам, Амир М.; Галил, Цви (2001), «Топологические нижние границы алгебраических машин произвольного доступа», SIAM Journal on Computing , 31 (3): 722–761, doi : 10.1137/S0097539797329397 .
^ Бен-Амрам, Амир М.; Беркман, Омер; Петерсен, Хольгер (2003), «Различность элементов на одноленточных машинах Тьюринга: комплексное решение», Acta Informatica , 40 (2): 81–94, doi : 10.1007/s00236-003-0125-8 , S2CID 24821585
^ Амбайнис, Андрис (2007), «Алгоритм квантового обхода для определения различимости элементов», SIAM Journal on Computing , 37 (1): 210–239, arXiv : quant-ph/0311001 , doi : 10.1137/S0097539705447311
^ Ши, Ю. (2002). Квантовые нижние оценки для проблем столкновений и различий элементов . Материалы 43-го симпозиума по основам информатики . стр. 513–519. arXiv : Quant-ph/0112086 . дои : 10.1109/SFCS.2002.1181975 .
^ Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым диапазоном» . Теория вычислений . 1 (1): 37–46. дои : 10.4086/toc.2005.v001a003 .
^ Кутин, С. (2005). «Квантовая нижняя граница для задачи столкновения с малым диапазоном» . Теория вычислений . 1 (1): 29–36. дои : 10.4086/toc.2005.v001a002 .
^ Мисра, Дж.; Грис, Д. (1982), «Нахождение повторяющихся элементов», Science of Computer Programming , 2 (2): 143–152, doi : 10.1016/0167-6423(82)90012-0 , hdl : 1813/6345 .

[1] Гил, Дж.; Мейер ауф дер Хайде, Ф.; Вигдерсон, А. (1990), «Не все ключи можно хешировать за постоянное время», Proc. 22-й симпозиум ACM по теории вычислений , стр. 244–253, doi : 10.1145/100216.100247 , S2CID 11943779 .

[2] Бен-Ор, Майкл (1983), «Нижние оценки для деревьев алгебраических вычислений», Proc. 15-й симпозиум ACM по теории вычислений , стр. 80–86, doi : 10.1145/800061.808735 .

[3] Григорьев Дима ; Карпински, Марек ; Хайде, Фридхельм Мейер; Смоленский, Роман (1996), «Нижняя оценка для рандомизированных алгебраических деревьев решений», Computational Complexity , 6 (4):357, doi : 10.1007/BF01270387 , S2CID 1462184 .

[4] Григорьев, Дима (1999), «Нижние границы сложности для рандомизированных деревьев вычислений над полями с нулевой характеристикой», Computational Complexity , 8 (4): 316–329, doi : 10.1007/s000370050002 , S2CID 10641238 .

[5] Бен-Амрам, Амир М.; Галил, Цви (2001), «Топологические нижние границы алгебраических машин произвольного доступа», SIAM Journal on Computing , 31 (3): 722–761, doi : 10.1137/S0097539797329397 .

[6] Бен-Амрам, Амир М.; Беркман, Омер; Петерсен, Хольгер (2003), «Различность элементов на одноленточных машинах Тьюринга: комплексное решение», Acta Informatica , 40 (2): 81–94, doi : 10.1007/s00236-003-0125-8 , S2CID 24821585

[7] Амбайнис, Андрис (2007), «Алгоритм квантового обхода для определения различимости элементов», SIAM Journal on Computing , 37 (1): 210–239, arXiv : quant-ph/0311001 , doi : 10.1137/S0097539705447311

[8] Ши, Ю. (2002). Квантовые нижние оценки для проблем столкновений и различий элементов . Материалы 43-го симпозиума по основам информатики . стр. 513–519. arXiv : Quant-ph/0112086 . дои : 10.1109/SFCS.2002.1181975 .

[9] Амбайнис, А. (2005). «Степень полинома и нижние границы квантовой сложности: столкновение и различие элементов с малым диапазоном» . Теория вычислений . 1 (1): 37–46. дои : 10.4086/toc.2005.v001a003 .

[10] Кутин, С. (2005). «Квантовая нижняя граница для задачи столкновения с малым диапазоном» . Теория вычислений . 1 (1): 29–36. дои : 10.4086/toc.2005.v001a002 .

[11] Мисра, Дж.; Грис, Д. (1982), «Нахождение повторяющихся элементов», Science of Computer Programming , 2 (2): 143–152, doi : 10.1016/0167-6423(82)90012-0 , hdl : 1813/6345 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]