Девид Дойч - Структура реальности

Ясно, что числа из огромного диапазона – безусловно содержащего любые числа, которые когда-либо были измерены как численные значения физических переменных – можно перемножить за крошечную долю секунды. Таким образом, умножение действительно легко поддается обработке для любых целей в пределах физики (или, по крайней мере, в пределах существующей физики). Вероятно, за пределами физики могут появиться практические причины умножения гораздо больших чисел. Например, для шифровальщиков огромный интерес представляют произведения простых чисел, состоящих примерно из 125 цифр. Наша гипотетическая машина могла бы умножить два таких простых числа, получив произведение, состоящее из 250 цифр, примерно за одну сотую секунды. За одну секунду она могла бы перемножить два тысячезначных числа, а современные компьютеры легко могут осуществить более точный расчет этого времени. Только некоторые исследователи эзотерических областей чистой математики заинтересованы в выполнении таких непостижимо огромных умножений, однако, мы видим, что даже у них нет причины считать умножение трудно обрабатываемым.

Напротив, разложение на множители, по сути процесс, обратный умножению, кажется гораздо сложнее. В начале вводится одно число, скажем, 10949769651859, задача заключается в том, чтобы найти два множителя, меньших числа, произведение которых равно 10949769651859. Поскольку мы только что умножили эти числа, мы знаем, что в этом случае ответ будет 4220851 и 2594209 (и поскольку оба эти числа простые, это единственно правильный ответ). Но не обладая таким внутренним знанием, как мы нашли бы эти множители? В поисках простого метода вы обратитесь к детским воспоминаниям, но впустую, поскольку такого метода не существует.

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

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

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

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