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

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