Theoretical Computer Science: взгляд математика

It is very easy to use this thing. Just imagine you have a Turing machine with random access  [1].
Из объяснения экскурсоводом Филадельфийского музея изящных искусств правил пользования аудиогидом

Александр Разборов - член-корреспондент РАН, работает в Математическом институте им. Стеклова РАН, в настоящий момент - в Институте перспективных исследований (Принстон, США). В 1990 году за работы в области теории сложности вычислений был удостоен премии Неванлинны Международного математического союза  [2].

Научная дисциплина с неоднозначно переводимым на русский язык названием Theoretical Computer Science (теоретическая компьютерная наука? или все-таки информатика? я в любом случае буду для краткости использовать аббревиатуру TCS) существует в виде, более-менее напоминающем современный, около сорока лет. Как подсказывают и название, и возраст, ее развитие, по существу, началось с появлением первых ЭВМ, и это, разумеется, не случайно. Именно тогда и именно по этой причине интерес многих специалистов по абстрактной теории алгоритмов (и в их числе нескольких выдающихся математических логиков того времени) начал постепенно смещаться от вопросов существования алгоритмов для тех или иных алгоритмических задач к изучению их эффективности и пригодности с практической точки зрения. Этот переход во многом стимулировался пониманием того, что даже для наиболее базисных задач эти две вещи далеко не одно и то же.

Например, имеются универсальные алгоритмы, позволяющие проверять истинность любого утверждения о вещественных числах (которое можно записать в стандартном языке математической логики первого порядка - отметим, что путем введения декартовых координат к такому виду можно привести, например, любую задачу элементарной геометрии). Первый такой алгоритм был придуман американским логиком Альфредом Тарским (Alfred Tarski) еще в 1948 году. Однако алгоритм Тарского оказался неэффективен со всех мыслимых точек зрения, а в 1974 году было строго доказано, что время работы любого алгоритма для этой задачи зависит по крайней мере экспоненциально от длины исходного утверждения.

Этот пример относится к области применения ЭВМ, считавшейся в 60-е годы чуть ли не единственной, которую я буду условно называть классические вычисления, в наиболее широком смысле этого термина. Отличительными чертами классического вычисления являются традиционная схема

Программа P + входные данные x ® вычислительное устройство ® ответ P(x)

и отсутствие интерактивности. Короче, классическое вычисление - это все, для чего вы можете использовать такие почтенные языки, как Алгол или Фортран, и не испытывать при этом существенных неудобств.

Общеизвестно, что изучение любого явления математическими методами становится возможным лишь после некоторых допущений, позволяющих абстрагироваться от ненужных деталей и при этом по возможности не утратить суть изучаемого явления. К числу наиболее важных допущений, принятых в теории сложности классических вычислений в 60-е годы и надолго определивших ее последующее развитие, относятся, в частности, следующие принципы.

ПЕРВЫЙ ПРИНЦИП. При фиксированном размере входных данных n сложность алгоритма (в этой роли могут выступать время работы, используемая память и т. д.) чаще всего измеряется «в наихудшем случае», то есть берется максимум по всем входным данным длины n. Постулируется, что для большинства разумных алгоритмов качество их работы не должно сильно зависеть от структуры исходных данных (коль скоро известна их битовая длина), а если это оказывается не так, то скорее всего плоха изначальная постановка задачи (не учтена какая-либо важная специфика).

ВТОРОЙ ПРИНЦИП. Алгоритмы изучаются с точки зрения их асимптотической сложности, то есть когда n стремится к бесконечности. Постулируется, что асимптотическое поведение в подавляющем большинстве случаев адекватно отражает поведение алгоритма для тех малых значений n, которые на самом деле представляют интерес.

ТРЕТИЙ ПРИНЦИП. Особое внимание уделяется алгоритмам, время работы которых ограничено некоторым полиномом от n. Постулируется, что в подавляющем большинстве случаев требование полиномиальности достаточно адекватно отражает «практическую осуществимость» алгоритма.

Как мы знаем, виртуальная реальность оказалась намного сложнее прогнозов, сделанных на заре компьютерной эры, и классические вычисления стали далеко не единственной сферой применения компьютеров. Все большее место завоевывала идея использования вычислительной техники в качестве удобного инструмента для реализации разнообразных интерактивных процессов: сетевых и криптографических протоколов, баз данных и т. д. Развитие TCS отражало эту эволюцию, как в зеркале, а во многих случаях предвосхищало и определяло ее.

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

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

Такое протяженное и по меньшей мере двойственное положение TCS, помимо очевидных преимуществ, предоставляемых междисциплинарностью, навлекает на ее голову поток критических замечаний, местами даже яростных. Любопытно (хотя и предсказуемо) при этом то, что сыплющиеся с двух сторон замечания имеют строго противоположную направленность и, соответственно, предлагают прямо противоположные действия по исправлению ситуации.

Любая честная и осмысленная дискуссия по этому поводу довольно быстро упирается в более общие вопросы о предназначении и путях развития любой фундаментальной науки, ожидаемой от нее отдачи, зачастую непростых взаимоотношениях с практикой и т. д. О таких деликатных материях лучше не писать вообще, чем делать это впопыхах, а даже самое сжатое изложение лишь нескольких соображений автора по этому поводу моментально превысило объем, отведенный под данное эссе. Поэтому я отсылаю заинтересованного читателя к его полной версии [0], а здесь ограничусь лишь парой примеров (призванных иллюстрировать тезис об относительной полезности TCS как фундаментальной науки).

Концепция криптографии с публичным (открытым) ключом возникла в TCS в рамках все той же «асимптотической» идеологии, на которой основана теория сложности вычислений. В частности, криптосистема RSA впервые появилась в 1978 году в строго математической статье, написанной тремя теоретиками Р. Ривестом (Rivest), А. Шамиром (Shamir) и Л. Адлеманом (Adleman). Хотя современная криптография давно является самостоятельной областью, в ней не существует ярко выраженного деления на «теоретическую» и «практическую», и значительная часть практически ценных результатов по сей день инициируется теоретическими исследованиями в рамках сформулированных нами общих принципов. В частности, среди статей, написанных всеми тремя авторами схемы RSA в 1999-2000 гг., добрая половина является строго математическими.

Создателем одной из самых известных и удачливых Интернет-компаний - Akamai - является профессор Массачусетского технологического института Том Лейтон (Tom Leighton), работающий в TCS-группе, а сама компания основана на одной из его математических теорем (см. www.akamai.com/html/en/ia/our_roots.html). Лейтон продолжает публиковать теоретические статьи и вообще остается активным членом TCS-сообщества, а добрая половина штатных сотрудников и внештатных консультантов Akamai привлечена из числа теоретиков (от полных профессоров  [4] до студентов), работающих в лучших американских университетах.

[i37930]