Рандомизированный алгоритм

Вероятностные структуры данных
Часть серии по
Фильтр Блума Счетчик мин. Эскиз Частный фильтр Пропустить список
Случайные деревья
Случайное двоичное дерево Treap Быстро исследуемое случайное дерево
Связанный
Рандомизированный алгоритм HyperLogLog
v т е

Рандомизированного алгоритма является алгоритм , который использует степень случайности как часть своей логики или процедуры. Алгоритм обычно использует равномерно случайные биты в качестве вспомогательных входных данных для управления своим поведением в надежде на достижение хорошей производительности в «среднем случае» по всем возможным вариантам случайного выбора, определяемым случайными битами; таким образом, либо время выполнения, либо выход (или и то, и другое) являются случайными величинами.

Следует различать алгоритмы, которые используют случайный ввод, чтобы они всегда заканчивались правильным ответом, но где ожидаемое время выполнения конечно ( алгоритмы Лас-Вегаса , например Quicksort ^[1] ), и алгоритмы, которые могут дать неверный результат ( алгоритмы Монте-Карло , например, алгоритм Монте-Карло для задачи MFAS ^[2] ) или не дают результата, либо сигнализируя об ошибке, либо не завершая работу. В некоторых случаях вероятностные алгоритмы являются единственным практическим средством решения проблемы. ^[3]

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

Мотивация

В качестве мотивирующего примера рассмотрим задачу поиска буквы « а » в массиве из n элементов.

Вход : массив из n ≥2 элементов, в котором половина - это буквы a , а другая половина - b .

Вывод : найдите « » в массиве.

Мы даем две версии алгоритма, один алгоритм Лас-Вегаса и один алгоритм Монте-Карло .

Алгоритм Лас-Вегаса:

findingA_LV ( массив  , п ) начинают повтор Произвольно выберите один элемент из из п элементов . до «а» будет найден конец

Этот алгоритм работает с вероятностью 1. Количество итераций варьируется и может быть сколь угодно большим, но ожидаемое количество итераций равно

{\ displaystyle \ lim _ {n \ to \ infty} \ sum _ {i = 1} ^ {n} {\ frac {i} {2 ^ {i}}} = 2}

Поскольку он постоянен, ожидаемое время выполнения для многих вызовов равно ${\ Displaystyle \ Theta (1)}$ . (См. Обозначение Big O )

Алгоритм Монте-Карло:

findingA_MC ( массив  , п , к ) начинается I : = 0 повтора Произвольно выбрать один элемент из из п элементов . i : = i + 1, пока не будет найдено i = k или 'a' конец

Если « a » найден, алгоритм успеха, иначе алгоритм не удается. После k итераций вероятность найти ' a ' равна:

${\ Displaystyle \ Pr [\ mathrm {найти ~ а}] = 1- (1/2) ^ {k}}$

Этот алгоритм не гарантирует успеха, но время выполнения ограничено. Количество итераций всегда меньше или равно k. Принимая k постоянным, время выполнения (ожидаемое и абсолютное) равно ${\ Displaystyle \ Theta (1)}$ .

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

В приведенном выше примере алгоритм Лас-Вегаса всегда возвращает правильный ответ, но время его выполнения является случайной величиной. Алгоритм Монте-Карло (связанный с методом Монте-Карло для моделирования) гарантированно завершится за время, которое может быть ограничено функцией размером входных данных и ее параметром k , но допускает небольшую вероятность ошибки . Обратите внимание, что любой алгоритм Лас-Вегаса можно преобразовать в алгоритм Монте-Карло (с помощью неравенства Маркова), выводя произвольный, возможно, неправильный ответ, если он не может быть завершен в течение указанного времени. И наоборот, если существует эффективная процедура проверки для проверки правильности ответа, то алгоритм Монте-Карло может быть преобразован в алгоритм Лас-Вегаса путем многократного выполнения алгоритма Монте-Карло, пока не будет получен правильный ответ.

Вычислительная сложность

Теория вычислительной сложности моделирует рандомизированные алгоритмы как вероятностные машины Тьюринга . И Лас - Вегас и Монте - Карло алгоритмы рассматриваются и некоторые классы сложности изучаются. Самым основным классом рандомизированной сложности является RP , который представляет собой класс задач решения, для которых существует эффективный (полиномиальное время) рандомизированный алгоритм (или вероятностная машина Тьюринга), который распознает NO-экземпляры с абсолютной уверенностью и распознает YES-экземпляры с вероятностью не менее 1/2. Класс дополнения для RP - co-RP. Классы проблем, имеющие (возможно, неограничивающие) алгоритмы с полиномиальным временемсреднее время работы случая, вывод которого всегда правильный, называется ZPP .

Класс проблем, для которых разрешено идентифицировать как YES, так и NO-экземпляры с некоторой ошибкой, называется BPP . Этот класс действует как рандомизированный эквивалент P , то есть BPP представляет класс эффективных рандомизированных алгоритмов.

История

Исторически первым рандомизированным алгоритмом был метод, разработанный Майклом О. Рабином для задачи ближайшей пары в вычислительной геометрии . ^[4] Изучение рандомизированных алгоритмов было стимулировано открытием в 1977 году рандомизированного теста на простоту (т. Е. Определения простоты числа) Робертом М. Соловаем и Фолькером Штрассеном . Вскоре после этого Майкл О. Рабин продемонстрировал, что критерий простоты Миллера 1976 года можно превратить в рандомизированный алгоритм. В то время не было известно практического детерминированного алгоритма простоты.

Тест на простоту Миллера – Рабина основан на бинарном соотношении между двумя положительными целыми числами k и n, которое можно выразить, сказав, что k «свидетельствует о составности» n . Можно показать, что

Если есть свидетель составности n , то n составное (т. Е. N не простое ), и
Если n составное, то по крайней мере три четверти натуральных чисел меньше n свидетельствуют о его составности, и
Существует быстрый алгоритм, который по данным k и n определяет, является ли k свидетелем составности n .

Заметим, что это означает, что проблема простоты находится в Co- RP .

Если случайным образом выбирается на 100 чисел меньше составного числа n , то вероятность не найти такого «свидетеля» составляет (1/4) ^100, так что для большинства практических целей это хороший тест на простоту. Если n большое, может не быть другого практического теста. Вероятность ошибки можно снизить до произвольной степени, выполнив достаточно независимых тестов.

Следовательно, на практике нет штрафа, связанного с принятием небольшой вероятности ошибки, поскольку с небольшой осторожностью вероятность ошибки может быть сделана астрономически малой. В самом деле, даже несмотря на то, что с тех пор был найден детерминированный тест на простоту за полиномиальное время (см. Тест на простоту AKS ), он не заменил старые вероятностные тесты в криптографическом программном обеспечении, и не ожидается, что он сделает это в обозримом будущем.

Примеры

Быстрая сортировка

Быстрая сортировка - это знакомый, часто используемый алгоритм, в котором может быть полезна случайность. Многим детерминированным версиям этого алгоритма требуется время O ( n ² ) для сортировки n чисел для некоторого четко определенного класса вырожденных входов (например, уже отсортированного массива) с конкретным классом входов, которые генерируют это поведение, определенное протоколом для поворотный выбор. Однако, если алгоритм выбирает поворотные элементы равномерно и случайным образом, он имеет доказуемо высокую вероятность завершения за время O ( n log n ) независимо от характеристик входных данных.

Рандомизированные инкрементальные конструкции в геометрии

В вычислительной геометрии стандартный метод построения такой структуры, как выпуклая оболочка или триангуляция Делоне, заключается в случайном перестановке входных точек, а затем их вставке по одной в существующую структуру. Рандомизация гарантирует, что ожидаемое количество изменений в структуре, вызванных вставкой, невелико, и поэтому ожидаемое время работы алгоритма может быть ограничено сверху. Этот метод известен как рандомизированное инкрементное строительство . ^[5]

Мин. Сокращение

Вход : график G ( V , E ).

Выход : а вырезать разбиения вершин в L и R , с минимальным числом ребер между L и R .

Напомним, что сжатие двух узлов, u и v , в (мульти-) графе дает новый узел u 'с ребрами, которые являются объединением ребер, инцидентных либо на u, либо на v , за исключением любого ребра (ребер), соединяющего u и v . На рисунке 1 приведен пример сжатия вершины A и B . После сжатия полученный граф может иметь параллельные ребра, но не содержать петель.

Рисунок 2: Успешный запуск алгоритма Каргера на 10-вершинном графе. Минимальный разрез имеет размер 3 и обозначен цветами вершин.

Рисунок 1: Сокращение вершин A и B

Базовый алгоритм Каргера ^[6] :

начинать я = 1 повторить  повторить Возьмем случайное ребро (u, v) ∈ E в G заменить u и v сокращением u ' пока не останется только 2 узла получить соответствующий результат разреза C _i я = я + 1 пока я = м вывести минимальный разрез среди C ₁ , C ₂ , ..., C _m .конец

При каждом выполнении внешнего цикла алгоритм повторяет внутренний цикл до тех пор, пока не останется только 2 узла, и будет получен соответствующий разрез. Время выполнения одного выполнения ${\ Displaystyle О (п)}$ , а n обозначает количество вершин. После m раз выполнения внешнего цикла мы выводим минимальное сокращение среди всех результатов. На рисунке 2 приведен пример одного выполнения алгоритма. После выполнения у нас получается вырез 3 размера.

Лемма 1 - Пусть к быть размером мин вырезать, и пусть $С = {е 1, е 2, ..., е к}$ быть мин покрой. Если во время итерации я , ни одно ребро $е \in C$ выбран для сжатия, то $С я = С$ .

Доказательство -

Если G не соединен, то G можно разделить на L и R без ребер между ними. Итак, минимальный разрез в несвязном графе равен 0. Теперь предположим, что G связен. Пусть $V = L \cup R$ - разбиение V, индуцированное $C : C = {{u, v} \in E : u \in L, v \in R}$ (определено правильно, поскольку G связна). Рассмотрим ребро { u ,v } из C . Изначально u , v - различные вершины. Пока мы выбираем край ${\ displaystyle f \ neq e}$ , $u$ и $v$ не объединяются. Таким образом, в конце алгоритма, мы имеем два составных узлов , охватывающие весь граф, один из которых состоят из вершин L , а других , состоящих из вершин R . Как и на рисунке 2, размер минимального разреза равен 1, а C = {( A , B )}. Если мы не выберем ( A , B ) для сокращения, мы можем получить минимальное сокращение.

Лемма 2 - Если G является мультиграфом с р вершинами и чья мин разрез имеет величину K , то G имеет по крайней мере рк / 2 ребер.

Доказательство -

Поскольку минимальный разрез равен k , каждая вершина v должна удовлетворять степени ( v ) ≥ k . Следовательно, сумма степеней не меньше pk . Но, как известно, сумма степеней вершин равна 2 | E |, Лемма следует.

Анализ алгоритма

Вероятность успеха алгоритма равна 1 - вероятность того, что все попытки потерпят неудачу. По независимости вероятность того, что все попытки потерпят неудачу, равна

{\ displaystyle \ prod _ {i = 1} ^ {m} \ Pr (C_ {i} \ neq C) = \ prod _ {i = 1} ^ {m} (1- \ Pr (C_ {i} = C)).}

По лемме 1 вероятность того, что $C i = C$ - это вероятность того, что ни одно ребро C не будет выбрано во время итерации i . Рассмотрим внутренний цикл и обозначим через $G j$ граф после j сжатий ребер, где $j \in {0, 1,\dots, n - 3}$ . $G j$ имеет $n - j$ вершин. Мы используем цепное правило условных возможностей . Вероятность того, что ребро, выбранное на итерации j , не входит в C , при условии, что никакое ребро C был выбран раньше, это ${\ displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}}}$ . Заметим, что $G j$ все еще имеет минимальный разрез размера k , поэтому по лемме 2 он все еще имеет не менее ${\ displaystyle {\ frac {(nj) k} {2}}}$ края.

Таким образом, ${\ displaystyle 1 - {\ frac {k} {| E (G_ {j}) |}} \ geq 1 - {\ frac {2} {nj}} = {\ frac {nj-2} {nj}} }$ .

Таким образом, по цепному правилу вероятность найти минимальный разрез C равна

{\ displaystyle \ Pr [C_ {i} = C] \ geq \ left ({\ frac {n-2} {n}} \ right) \ left ({\ frac {n-3} {n-1}} \ right) \ left ({\ frac {n-4} {n-2}} \ right) \ ldots \ left ({\ frac {3} {5}} \ right) \ left ({\ frac {2} {4}} \ right) \ left ({\ frac {1} {3}} \ right).}

Отмена дает ${\ displaystyle \ Pr [C_ {i} = C] \ geq {\ frac {2} {n (n-1)}}}$ . Таким образом, вероятность успеха алгоритма не менее ${\ displaystyle 1- \ left (1 - {\ frac {2} {n (n-1)}} \ right) ^ {m}}$ . Для ${\ Displaystyle м = {\ гидроразрыва {п (п-1)} {2}} \ пер п}$ , это эквивалентно ${\ displaystyle 1 - {\ frac {1} {n}}}$ . Алгоритм находит минимальный разрез с вероятностью ${\ displaystyle 1 - {\ frac {1} {n}}}$ , во время ${\ Displaystyle О (мн) = О (п ^ {3} \ журнал п)}$ .

Дерандомизация

Случайность можно рассматривать как ресурс, как пространство и время. Дерандомизация - это процесс удаления случайности (или ее минимального использования). В настоящее время неизвестно, можно ли дерандомизировать все алгоритмы без значительного увеличения времени их работы. Например, с точки зрения вычислительной сложности неизвестно, является ли P = BPP , т. Е. Мы не знаем, можем ли мы взять произвольный рандомизированный алгоритм, который выполняется за полиномиальное время с небольшой вероятностью ошибки, и дерандомизировать его для работы за полиномиальное время без использования случайности. .

Существуют определенные методы, которые можно использовать для дерандомизации определенных рандомизированных алгоритмов:

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

Где помогает случайность

Когда модель вычислений ограничивается машинами Тьюринга , в настоящее время остается открытым вопрос, позволяет ли способность делать случайный выбор решать некоторые задачи за полиномиальное время, которые не могут быть решены за полиномиальное время без этой возможности; это вопрос, является ли P = BPP. Однако в других контекстах есть конкретные примеры проблем, в которых рандомизация приводит к строгим улучшениям.

Основываясь на начальном мотивирующем примере: учитывая экспоненциально длинную строку из 2 ^k символов, половину a и половину b, машине с произвольным доступом требуется 2 ^{k -1} поисков в худшем случае, чтобы найти индекс a ; если разрешено делать случайный выбор, он может решить эту проблему за ожидаемое полиномиальное число поисков.
Естественный способ выполнения числовых вычислений во встроенных системах или киберфизических системах - обеспечить результат, который с высокой вероятностью приближается к правильному (или, вероятно, приблизительно правильному вычислению (PACC)). Сложная проблема, связанная с оценкой потери несоответствия между приближенным и правильным вычислением, может быть эффективно решена путем обращения к рандомизации ^[7]
В связи со сложностью связи равенство двух строк может быть проверено с некоторой надежностью с помощью ${\ displaystyle \ log n}$ биты связи с рандомизированным протоколом. Любой детерминированный протокол требует ${\ Displaystyle \ Theta (п)}$ биты при защите от сильного противника. ^[8]
Объем выпуклого тела можно оценить с помощью рандомизированного алгоритма с произвольной точностью за полиномиальное время. ^[9] Барани и Furedi показал , что ни один детерминированный алгоритм не может сделать то же самое. ^[10] Это верно безоговорочно, т. Е. Не полагаясь на какие-либо предположения теории сложности, предполагая, что выпуклое тело может быть запрошено только как черный ящик.
Более теоретически сложный пример места, где случайность, кажется, помогает, - это класс IP . IP состоит из всех языков, которые могут быть приняты (с большой вероятностью) полиномиально долгим взаимодействием между всемогущим доказывающим устройством и верификатором, реализующим алгоритм BPP. IP = PSPACE . ^[11] Однако, если требуется, чтобы верификатор был детерминированным, то IP = NP .
В сети химических реакций (конечный набор реакций, таких как A + B → 2C + D, действующих на конечное число молекул), возможность когда-либо достичь заданного целевого состояния из начального состояния является разрешимой, при этом даже приближаясь к вероятности когда-либо достижение заданного целевого состояния (с использованием стандартной основанной на концентрации вероятности, для которой реакция будет следующей) неразрешимо. Более конкретно, ограниченная машина Тьюринга может быть смоделирована со сколь угодно высокой вероятностью правильной работы в течение всего времени, только если используется случайная сеть химических реакций. С простой недетерминированной сетью химических реакций (любая возможная реакция может произойти следующей) вычислительная мощность ограничивается примитивными рекурсивными функциями . ^[12]

См. Также

Вероятностный анализ алгоритмов
Алгоритм Атлантик-Сити
Алгоритм Монте-Карло
Алгоритм Лас-Вегаса
Богосорт
Принцип отложенного решения
Рандомизированные алгоритмы как игры с нулевой суммой
Вероятностная дорожная карта
HyperLogLog
count – min эскиз
приблизительный алгоритм подсчета

Примечания

Перейти ↑ Hoare, CAR (июль 1961 г.). «Алгоритм 64: Быстрая сортировка». Commun. ACM . 4 (7): 321–. DOI : 10.1145 / 366622.366644 . ISSN 0001-0782 .
^ Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи о множестве дуг с минимальной обратной связью». Прикладные программные вычисления . 41 : 235–246. DOI : 10.1016 / j.asoc.2015.12.018 .
^ «При проверке простоты очень больших чисел, выбранных наугад, шанс наткнуться на значение, которое обманывает тест Ферма, меньше, чем шанс того, что космическое излучение заставит компьютер сделать ошибку при выполнении« правильного »алгоритма. Рассмотрение алгоритма неадекватным по первой причине, но не по второй, иллюстрирует разницу между математикой и инженерией ». Хэл Абельсон и Джеральд Дж. Сассман (1996). Структура и интерпретация компьютерных программ . MIT Press , раздел 1.2 .
^ Шмид, Михель. Ближайшие точечные задачи вычислительной геометрии. Max-Planck-Institut für Informatik | год = 1995
^ Зайдель Р. Обратный анализ рандомизированных геометрических алгоритмов .
^ А.А. Цай, В.С. Лавджой, Дэвид Р. Каргер, Случайная выборка в задачах вырезания, потока и проектирования сети , Математика исследования операций, 24 (2): 383–413, 1999.
^ Alippi Чезаре (2014), разведки для встраиваемых систем , Springer, ISBN 978-3-319-05278-6.
^ Kushilevitz, Эяль; Нисан, Ноам (2006), сложность коммуникации , Cambridge University Press, ISBN 9780521029834. Детерминированную нижнюю оценку см. На стр. 11; относительно логарифмической рандомизированной верхней границы см. стр. 31–32.
^ Дайер, М .; Frieze, A .; Kannan, R. (1991), "Случайный алгоритм полиномиальное время для аппроксимации объем выпуклых тел" (PDF) , Журнал ACM , 38 (1): 1-17, DOI : 10,1145 / 102782,102783
^ Füredi, Z .; Bárány, I. (1986), "Вычислить объем сложно", Proc. Восемнадцатый ACM симпозиум по теории вычислений (Беркли, Калифорния, 28-30 мая 1986 г.) (PDF) , Нью - Йорк, Нью - Йорк: АКМ, С. 442-447,. CiteSeerX 10.1.1.726.9448 , DOI : 10,1145 / 12130,12176 , ISBN 0-89791-193-8
^ Шамир, А. (1992), "IP = PSPACE", Журнал ACM , 39 (4): 869-877, DOI : 10,1145 / 146585,146609
^ Кук, Мэтью ; Соловейчик, Давид; Уинфри, Эрик ; Брук, Иегошуа (2009), «Программируемость сетей химических реакций», в Кондоне, Энн ; Харел, Дэвид ; Kok, Joost N .; Саломаа, Арто ; Уинфри, Эрик (ред . ), Алгоритмический Биологические процессы (PDF) ., Natural Computing Series, Springer-Verlag, стр 543-584, DOI : 10.1007 / 978-3-540-88869-7_27 .

Ссылки

Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw – Hill, 1990. ISBN 0-262-03293-7 . Глава 5: Вероятностный анализ и рандомизированные алгоритмы, стр. 91–122.
Дирк Драхейм. « Семантика вероятностного типизированного лямбда-исчисления (семантика цепи Маркова, поведение завершения и денотационная семантика) », Springer, 2017.
Джон Клейнберг и Ива Тардос . Разработка алгоритмов . Глава 13: «Рандомизированные алгоритмы».
Фаллис, Д. (2000). «Надежность рандомизированных алгоритмов». Британский журнал философии науки . 51 (2): 255–271. DOI : 10.1093 / bjps / 51.2.255 .
М. Митценмахер и Э. Упфаль . Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ . Издательство Кембриджского университета, Нью-Йорк (Нью-Йорк), 2005.
Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы . Издательство Кембриджского университета, Нью-Йорк (Нью-Йорк), 1995.
Раджив Мотвани и П. Рагхаван. Рандомизированные алгоритмы . Обзор рандомизированных алгоритмов.
Христос Пападимитриу (1993), вычислительная сложность (1-е изд.), Аддисон Уэсли, ISBN 978-0-201-53082-7 Глава 11: Рандомизированные вычисления, стр. 241–278.
Рабин, Майкл О. (1980). «Вероятностный алгоритм проверки простоты» . Журнал теории чисел . 12 : 128–138. DOI : 10.1016 / 0022-314X (80) 90084-0 .
А.А. Цай, В.С. Лавджой, Дэвид Р. Каргер, Случайная выборка в задачах разрезания, потока и проектирования сети , Математика исследования операций, 24 (2): 383–413, 1999.

[1] Перейти ↑ Hoare, CAR (июль 1961 г.). «Алгоритм 64: Быстрая сортировка». Commun. ACM . 4 (7): 321–. DOI : 10.1145 / 366622.366644 . ISSN 0001-0782 .

[2] Куделич, Роберт (2016-04-01). «Рандомизированный алгоритм Монте-Карло для задачи о множестве дуг с минимальной обратной связью». Прикладные программные вычисления . 41 : 235–246. DOI : 10.1016 / j.asoc.2015.12.018 .

[3] «При проверке простоты очень больших чисел, выбранных наугад, шанс наткнуться на значение, которое обманывает тест Ферма, меньше, чем шанс того, что космическое излучение заставит компьютер сделать ошибку при выполнении« правильного »алгоритма. Рассмотрение алгоритма неадекватным по первой причине, но не по второй, иллюстрирует разницу между математикой и инженерией ». Хэл Абельсон и Джеральд Дж. Сассман (1996). Структура и интерпретация компьютерных программ . MIT Press , раздел 1.2 .

[4] Шмид, Михель. Ближайшие точечные задачи вычислительной геометрии. Max-Planck-Institut für Informatik | год = 1995

[5] Зайдель Р. Обратный анализ рандомизированных геометрических алгоритмов .

[6] А.А. Цай, В.С. Лавджой, Дэвид Р. Каргер, Случайная выборка в задачах вырезания, потока и проектирования сети , Математика исследования операций, 24 (2): 383–413, 1999.

[7] Alippi Чезаре (2014), разведки для встраиваемых систем , Springer, ISBN 978-3-319-05278-6.

[8] Kushilevitz, Эяль; Нисан, Ноам (2006), сложность коммуникации , Cambridge University Press, ISBN 9780521029834. Детерминированную нижнюю оценку см. На стр. 11; относительно логарифмической рандомизированной верхней границы см. стр. 31–32.

[9] Дайер, М .; Frieze, A .; Kannan, R. (1991), "Случайный алгоритм полиномиальное время для аппроксимации объем выпуклых тел" (PDF) , Журнал ACM , 38 (1): 1-17, DOI : 10,1145 / 102782,102783

[10] Füredi, Z .; Bárány, I. (1986), "Вычислить объем сложно", Proc. Восемнадцатый ACM симпозиум по теории вычислений (Беркли, Калифорния, 28-30 мая 1986 г.) (PDF) , Нью - Йорк, Нью - Йорк: АКМ, С. 442-447,. CiteSeerX 10.1.1.726.9448 , DOI : 10,1145 / 12130,12176 , ISBN 0-89791-193-8

[11] Шамир, А. (1992), "IP = PSPACE", Журнал ACM , 39 (4): 869-877, DOI : 10,1145 / 146585,146609

[12] Кук, Мэтью ; Соловейчик, Давид; Уинфри, Эрик ; Брук, Иегошуа (2009), «Программируемость сетей химических реакций», в Кондоне, Энн ; Харел, Дэвид ; Kok, Joost N .; Саломаа, Арто ; Уинфри, Эрик (ред . ), Алгоритмический Биологические процессы (PDF) ., Natural Computing Series, Springer-Verlag, стр 543-584, DOI : 10.1007 / 978-3-540-88869-7_27 .

[1]