Структура реальности. Наука параллельных вселенных

Самый очевидный метод разложения на множители — делить вводимое число на все возможные множители, начиная с 2 и продолжая каждым нечётным числом, до тех пор, пока введённое число не разделится без остатка. По крайней мере, один из множителей (с учётом того, что введённое число не является простым) не может быть больше квадратного корня введённого числа, и это позволяет оценить, сколько времени может потребовать данный метод. В рассматриваемом случае наш компьютер найдёт меньший из двух множителей, 2 594 209, примерно за секунду с небольшим. Однако если исходное число будет в десять раз больше, а его квадратный корень примерно в три раза больше, то разложение его на множители по этому методу займёт в три раза больше времени. Другими словами, увеличение вводимого числа на один разряд уже утроит время обработки. Увеличение его ещё на один разряд снова утроит это время и т. д. Таким образом, время обработки будет увеличиваться в геометрической прогрессии, т. е. экспоненциально, с увеличением количества разрядов в раскладываемом на множители числе. Разложение на множители числа с 25-значными множителями по этому методу заняло бы все компьютеры на Земле на несколько веков.

Этот метод можно усовершенствовать, однако всем современным методам разложения числа на множители присуще это свойство экспоненциального роста. Самое большое число, которое было «в гневе» (а это было действительно так) разложено на множители, — число, сомножители которого тайно выбрали одни математики, чтобы бросить вызов другим математикам, — имело 129 цифр[38]. Разложение на множители выполнили с помощью сети Интернет глобальными совместными усилиями, в которых были задействованы тысячи компьютеров. Знаменитый специалист по алгоритмам Дональд Кнут[39] оценил, что разложение на множители 250-значного числа при использовании самых эффективных из известных методов, с помощью сети, состоящей из миллиона компьютеров, заняло бы более миллиона лет. Такие вещи трудно оценить, но даже если Кнут был чрезмерно пессимистичен, то нужно взять числа всего на несколько разрядов большие, и задача во много раз усложнится. Именно это мы имеем в виду, когда говорим, что разложение на множители больших чисел — труднорешаемая задача. Всё это очень сильно отличается от умножения, где, как мы видели, операцию с парой 250-значных чисел можно выполнить на домашнем компьютере. Никто не может даже представить себе, как можно разложить на множители числа, состоящие из тысячи или миллиона цифр.

По крайней мере, никто не мог этого представить до недавнего времени.

В 1982 году физик Ричард Фейнман[40] занимался компьютерным моделированием квантово-механических объектов. Его отправной точкой был факт, известный уже в течение некоторого времени, важность которого, однако, ещё не была оценена, а именно, что задача предсказания поведения квантово-механических систем (или, как мы можем это переформулировать — воспроизведения квантово-механических сред в виртуальной реальности) в общем случае является труднорешаемой. Одна из причин, по которой важность этого недооценивали, состояла в том, что никто и не ожидал особенно лёгкого предсказания интересных физических явлений с помощью компьютера. Возьмите, например, прогноз погоды или землетрясения. Несмотря на то что нужные уравнения известны, все знают, как трудно применять их в реальных ситуациях. В последнее время к этому привлекли широкое внимание в популярных книгах и статьях о хаосе и «эффекте бабочки». Но не эти эффекты ответственны за трудности, с которыми столкнулся Фейнман, по той простой причине, что они имеют место только в классической физике — то есть не в реальности, поскольку реальность квантово-механическая. Тем не менее я хочу сделать несколько замечаний относительно «хаотических» движений в классике, только чтобы подчеркнуть глубоко различный характер классической и квантовой непредсказуемости.