О пользе и привлекательности хаоса
(навеяно всплывшим обсуждением дискордианства у пользователя tiphareth)

Зачем вообще нужна случайность? Первое, что приходит в голову -
рандомизированные алгоритмы. Преступная пробабилитность часто либо
ускоряет известные алгоритмы в смысле асимптотики или хотя бы
константы перед ней, либо упрощает сам алгоритм. Самое простое -
хотя бы quicksort. Берем случайный элемент массива, делим массив
на меньшие и большие него, матожидание и ЗБЧ говорят нам, что он
разбился примерно пополам, "можем повторить".

f(2n) = 2f(n) + n, f(n) ~ n log n.

Чтобы это сделать без рандомизации, нам надо гарантированно найти
у массива середину ("медиану") за линейное время. Это вполне
решаемая проблема, но алгоритм там далеко не такой простой и
вообще это вполне неочевидная задача, кажется, чуть ли не первая
такая, встречающаяся в околошкольном программировании (см.
Кормен/Лейзерсон/Ривест/Штейн).

Другой популярный пример - это тест простоты Миллера-Рабина,
использующийся в RSA-шифровании, например. Случайно выбираем
свидетеля простоты, у простых чисел все числа такие
свидетели, у составных - меньше четверти, "можем повторить".

Чтобы проверить на свидетельство простоты, надо возводить
в степень, тыры-пыры, сложность работы для фиксированной
вероятности не влететь кубическая от длины десятичной записи,
если исхитриться, можно ужать до квадратичной.

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

Примеров таких очень много. Из свежемодного, начальное состояние
нейросетей перед обучением рандомизируют, чтобы не застряло, и
сам процесс обучения обычно рандомизированный модернизированный
градиентный спуск; из старомодного - Монте-Карло для всяких ядерных
и не очень физиков.

Ну и кроме этого откуда вообще берется иллюзия свободы воли, и
почему свобода полезна, а не только прекрасна как мазня Джорджии
О'Кифф. Зайцу полезно быть непредсказуемым для лисы, лисе - для
зайца. Животные, зажатые на узкой кривой конфигурационного
пространства, радуют своих напарников по пищевому поведению
и расстраивают свои (думающие только о себе) гены.

Наконец, оптимальные стратегии обычно смешанные, а не чистые.

Все это привело во второй половине 20 века Колмогорова и ко
к мысли о фактическом знаке равенства между сложностью и
случайностью. И это почти все, что мы знаем сейчас о сложности.

Однако (и на этом ода хаосу завершается) обычно мы хотим
от сложности чего-то ещё, кроме траектории броуновского движения.

Этого тоже следовало бы коснуться.

P.S. чуть не забыл, эпиграф в конце -


В трудные минуты на помощь Рэю приходила музыка. Как и многие туреттики, он был необыкновенно музыкален и едва ли выжил бы – как духовно, так и материально, – если бы не джаз. Он был известным барабанщиком-любителем, настоящим виртуозом, славившимся среди коллег и слушателей внезапными бурными экспромтами. Тики и навязчивые удары по барабану перерастали у него в изумительные импровизации, в ходе которых неожиданные, грубые вторжения болезни превращались в музыку. Туреттизм также давал Рэю преимущество в спортивных играх, особенно в настольном теннисе, где он побеждал отчасти вследствие аномально быстрых рефлексов и реакций, но главным образом опять же благодаря импровизациям, внезапным, нервным и, как он сам их описывал, легкомысленным ударам. Удары эти были настолько неожиданны, что почти всегда заставали противника врасплох.