Структура реальности

Насколько эффективно можно передать данные аспекты реальности? Другими словами, какие вычисления можно практически выполнить за данное время и при данных финансовых возможностях? Это основной вопрос теории вычислительной сложности, которая, как я уже сказал, занимается изучением ресурсов, необходимых для выполнения данных вычислительных задач. Теория сложности все еще в достаточной степени не объединена с физикой и потому не дает много количественных ответов. Однако она достигла успеха в определении полезного приближенного различия между легко- и труднообрабатываемыми вычислительными задачами. Общий подход лучше всего проиллюстрировать на примере. Рассмотрим задачу умножения двух достаточно больших чисел, скажем. 4 220 851 и 2594209. Многие из нас помнят тот метод умножения, которому мы научились в детстве. Нужно по очереди перемножить каждую цифру одного числа на каждую цифру другого и, сложив результаты, дать окончательный ответ, в данном случае 10949769651859. Вероятно, многие не захотят признать, что эта утомительная процедура делает умножение «легко обрабатываемым» хоть в каком-то обыденном смысле этого слова. (В действительности, существуют более эффективные методы умножения больших чисел, но этот весьма нагляден). Однако с точки зрения теории сложности, которая имеет дело с массивными задачами, решаемыми компьютерами которые не подвержены скуке и почти никогда не ошибаются, этот метод определенно попадает в категорию «легко обрабатываемых».

В соответствии со стандартным определением для «легкости обработки» важно не действительное время, затрачиваемое на умножение конкретной пары чисел, а важен факт, что при применении того же самого метода даже к большим числам, время увеличивается не слишком резко. Возможно это удивит вас, но этот весьма косвенный метод определения легкости обработки очень хорошо работает на практике для многих (хотя и не всех) важных классов вычислительных задач. Например, при умножении нетрудно увидеть, что стандартный метод можно использовать для умножения чисел, скажем, в десять раз больших, Приложив совсем незначительные дополнительные усилия. Ради доказательства предположим, что каждое элементарное умножение одной цифры на другую занимает у определенного компьютера одну микросекунду (включая время, необходимое для сложения, переходов и других операций, сопровождающих каждое элементарное умножение). При умножении семизначных чисел 4220851 и 2594209 каждую из семи цифр первого числа нужно умножить на каждую из семи цифр второго числа. Таким образом, общее время, необходимое для умножения (если операции выполняются последовательно), будет равно семи, умноженному на семь, или 49 микросекундам. При введении чисел, примерно в десять раз больших, содержащих по восемь цифр, время, необходимое для их умножения, будет равно 64 микросекундам: увеличение составляет всего 31%.

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

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