Вычислительная сложность
Мой шестой аргумент основан на понятии вычислительной сложности – хорошо разработанной математической теории, которая описывает сложность разрешения некоторых вычислительных проблем. Пока мы не изобретем машины, основанные на еще неизвестных формах вычисления, даже экспоненциальные улучшения не помогут нам из-за существования фундаментальных пределов возможного для компьютеров.
Закон Мура – увеличение мощности компьютеров каждые два года – убедил нас в том, что технологический прогресс сможет решить большинство вычислительных задач[30]. Мы живем в экспоненциальное время, и экспоненциальные улучшения в вычислительной мощности дают повод верить, что нам остается подождать нужного поколения компьютеров. Через десять лет машины станут в тысячу раз мощнее, чем нынешние компьютеры. Через двадцать лет – в миллион раз. Через тридцать – в миллиард. То есть можно с уверенностью сказать, что однажды компьютеры будут владеть такой вычислительной мощностью, что мы сможем делать с их помощью все, что захотим? К сожалению, это предположение далеко от правды.
Ученые разработали серьезную теорию вычислительной сложности. Она описывает, сколько вычислений нужно, чтобы решить разные проблемы конкретным или абстрактным способом. Для теории вычислительной сложности не имеет значения, какой именно компьютер используется. Это может быть персональный компьютер, смартфон или умные часы. Разница в устройстве обусловливает только разницу во времени выполнения задачи, ее постоянный коэффициент. То, что нас интересует, касается гораздо больших изменений во времени выполнения, чем постоянный коэффициент задачи. Для нас важен экспоненциальный рост, и, как мы увидим в дальнейшем, даже больше, чем экспоненциальный.
Допустим, вы хотите вычислить наибольшее число в списке. Это – линейная проблема. Вам необходимо просканировать весь список. Этот процесс займет время, пропорциональное количеству входных данных, то есть объему списка. Если список удвоить, это займет в два раза больше времени. Если утроить – в три раза.
А теперь представим, как можно упорядочить этот список – от меньшего к большему. Простейший метод заключается в том, чтобы найти для начала меньший пункт; как мы только что выяснили, это займет пропорциональное объему списка время. Затем необходимо найти предпоследнюю по величине вещь и т. д. В итоге время, которое нужно потратить на сортировку этого или любого другого списка, увеличивается в геометрической прогрессии. Если удвоить длину списка, это займет в четыре раза больше времени. Если утроить – в девять раз. Если учетверить – в шестнадцать. Звучит так себе. Однако вычисления могут масштабироваться еще хуже.
Существуют такие вычислительные проблемы, в которых время выполнения растет экспоненциально вместе с объемом входных данных. Представьте себе такую задачу: супруги при разводе хотят поделить свое имущество на две равноценные части. Простейший метод решения – это высчитать сумму каждой возможной комбинации вещей. Если стоимость одной из таких комбинаций равна половине стоимости всего имущества, то ответ найден. Каждый раз к входным данным – списку вещей – прибавляется одна единица, количество комбинаций, которые надо учитывать, удваивается, как и (в худшем случае) время выполнения алгоритма.
Хорошие новости заключаются в том, что экспоненциальный рост вычислительной мощности поможет решить подобные проблемы. Каждое удвоение мощности позволит выполнить задачу, в которой на одну вещь больше. Каков бы ни был объем входных данных, в конце концов он попадет в этот диапазон. Для того чтобы обработать информацию, включающую в себя на десять единиц больше возможного, нужно просто подождать еще десять поколений компьютеров.
Однако есть и вычислительные задачи, в которых время выполнения увеличивается быстрее. В таком случае экспоненциальный рост не спасет. Например, проблема вычисления площади множества Мандельброта. Множество Мандельброта – это тот прекрасный фрактал, который выглядит как спирали и морские коньки. Его называют самым сложным числом в математике.
Нам известно, что площадь множества Мандельброта ограничена. Этот фрактал находится внутри круга радиуса два, а его площадь соответственно меньше 4π (=12,566…). Однако высчитать его точную площадь, как нам известно, очень непросто. Лучший возможный метод – это медленно вычислять точки площади. Нужно сложить 10118 членов, чтобы высчитать площадь с точностью до сотых, 101181 – с точностью до тысячных. 10118 – это больше, чем атомов во Вселенной. Экспоненциальный рост не поможет справиться с такими сложными вычислительными задачами.
30
Закон Мура назван в честь Гордона Мура, сооснователя компаний Fairchild Semiconductor и Intel. В 1965 году он описал ежегодное удвоение количества компонентов на интегральной схеме. В 1975 году он округлил срок до двух лет. Закон Мура действовал больше пятидесяти лет. Мало кто знает, что он устарел уже несколько лет назад. Любой экспоненциальный тренд, существующий в реальном мире, рано или поздно заканчивается. В этом случае проблема заключалась в квантовых пределах. International Technology Roadmap for Semiconductors (ITRS) – это отраслевой орган, который, как следует из его названия, разрабатывает «дорожную карту» для достижения закона Мура. В 2014-м ITRS объявил о том, что цель индустрии больше не заключается в удвоении компонентов каждые два года. Учитывая, что теперь это не входит в планы больших компаний, производящих микропроцессоры, мы можем быть уверены в том, что этого не произойдет. Никто не собирается тратить миллиарды долларов, необходимых для изготовления следующего поколения станков для производства чипов, чтобы еще больше сократить размеры транзисторов. Любопытно, что нынешние цели Intel – это уменьшить потребление энергии, чтобы мобильные устройства могли иметь больше вычислительной мощности.