Структуры данных и алгоритмы cs.DS

Выделить один бракованный микрочип из миллиона, не имея ни малейшего представления о том, как выглядит дефект, — классическая задача поиска иголки в стоге сена. Обычный компьютер стал бы перебирать чипы один за другим. Квантовый же действует как самонастраивающийся дуршлаг: вы высыпаете всю партию разом, и лишь редкие дефектные экземпляры «загораются» — без какого-либо предварительного описания брака.

Бальный зал наполняется гостями. Каждое появление нового человека — это запрос, и задача распорядителя танцев — найти подходящую пару. Можно свести двоих сразу, как только они окажутся недалеко друг от друга, и тогда пара сложится точно, но вдруг через минуту появится идеальный партнёр? Если же медлить, копится усталость ожидающих: кто-то начинает скучать, кто-то теряет терпение.

Осень 1956 года. Курт Гёдель выводит на листе бумаги вопрос, обращённый к умирающему Джону фон Нейману: можно ли проверить выполнимость булевой формулы быстрее, чем полным перебором? Ответ придёт через 69 лет — и окажется укусом логического уробороса, мифического змея, поедающего собственный хвост. Змей рождается из случайности.