33-й ежегодный симпозиум по теории вычислений

Специалисты по теоретической информатике хорошо знакомы с двумя сокращениями: STOC и FOCS. Под ними скрываются две главные конференции по этой отрасли науки - Simposium on Theory of Computing и Foundations of Computer Science. По просьбе редакции "КТ" об очередной конференции STOC рассказывает один из ее участников.

Специалисты по теоретической информатике (Theoretical Computer Science, TCS) хорошо знакомы с двумя сокращениями: STOC и FOCS. Под ними скрываются две главные конференции по этой отрасли науки - Simposium on Theory of Computing (весенняя) и Foundations of Computer Science (осенняя). По просьбе редакции «КТ» об очередной конференции STOC (июль 2001, Крит) рассказывает один из ее участников.

Об этом подробно писал в «КТ» #379 Александр Разборов, один из наиболее известных специалистов в этой области. Коротко повторю: это раздел математики, связанный с понятием алгоритма (оценки сложности, языки для записи алгоритмов и многое другое). К словам Разборова добавлю лишь одно соображение. Наивно представлять себе пользу математики так: математики доказали теорему, а потом инженеры ее применили. Реальная польза в другом: разобравшись в теории, человек имеет больше шансов придумать что-нибудь практически полезное, используя родственные идеи. Так вот, изучение TCS, как показывает опыт, очень полезно будущим программистам.

Эти конференции посвящены анализу алгоритмов и их сложности и почти не касаются других разделов TCS (скажем, логических методов анализа программ), зато в своей области отражают значительную часть наиболее интересных результатов. Традиционно они проходят в Америке. Нынешняя STOC была (едва ли не единственным) исключением: она состоялась на родине Минотавра - Крите. Дать обзор всех докладов (было отобрано 83 из 230 представленных) нет никакой возможности, но кое о чем рассказать попробую ¹.

Многие доклады были посвящены модной теме - квантовым вычислениям. Когда хотят получить деньги на исследования в этой области, обычно подчеркивают, что квантовые компьютеры (если их вдруг сделают, и притом достаточно мощными) позволят быстро решать некоторые задачи, для которых неизвестны (классические) эффективные алгоритмы. В первую очередь это относится к разложению чисел на множители (после чего рухнет значительная часть современной криптографии). Но вопрос о квантовых вычислениях имеет более глубокий смысл и для физики, и для теории вычислений. С точки зрения теории вычислений: каковы физические ограничения на устройства переработки информации? Каковы могут быть вычислительные возможности компьютера, который занимает один кубический метр, выдает ответ через секунду после вопроса с вероятностью не менее 90% и потребляет не более ватта?

Современные законы физики (прежде всего квантовой механики) не позволяют утверждать, что возможности вычислительных устройств ограничены классом полиномиальных алгоритмов ² - моделирование законов квантовой механики не удалось уложить в такие рамки. А если физический прибор способен решать неполиномиальные задачи, то какие именно? Можно ли указать среди них «естественные» задачи?

Для физики: на границе микро- и макромира традиционно возникают парадоксы и пробелы (необратимость времени в термодинамике при обратимости в механике, процесс измерения в квантовой механике, где свойства измерительного прибора постулируются, а не выводятся из базовых законов). Именно на этой границе и должны возникнуть будущие квантовые компьютеры. Если раньше физики (с видимой неохотой - уж очень это отдавало философией) рассуждали о мысленных экспериментах вроде демона Максвелла, то теперь обсуждаются реальные эксперименты и конкретные устройства, и дело - можно надеяться - пойдет лучше…

Ежегодная премия Тьюринга (Alan Turing) присуждается ACM (Association for Computing Machinery) в качестве «most prestigious technical award» ³. Она присуждается не одним теоретикам - например, ее получили не только Кеннет Томпсон (Kenneth Thompson) и Деннис Ритчи (Dennis Ritchie), разработчики Unix, что еще можно понять, но и Фредерик Брукс (Frederick Brooks), автор знаменитой книги «The Mythical Man-Month» («Мифический человеко-месяц»), в которой он рассказывает о своих попытках руководить разработкой программного обеспечения, в частности, для машин серии IBM/360. (Очень поучительная книга, кстати. Там, в частности, написано, что невозможно быть уверенным в правильности большой программы, ибо в ней может быть тысяча условных переходов и для их тестирования понадобится 21000 примеров. Интересно, сколько непрерывных функций понадобилось бы ему для тестирования теоремы о промежуточных значениях?..)

В этом году премию Тьюринга получил Эндрю Яо (Andrew Chi-Chih Yao). По традиции лауреат читает лекцию (сборник таких лекций был переведен издательством «Мир»). Яо посвятил ее обзору основных достижений и проблем теоретической информатики.

Вот очень краткий пересказ его выступления.

• В начале 1970-х годов мы научились сводить одну проблему к другой. Тем самым множество загадок (почему те или иные задачи трудные?) сводится к одной загадке.

• Возникли новые интересные постановки задач (вероятностные алгоритмы, коммуникационная сложность, криптография, односторонние функции и псевдослучайность, интерактивные доказательства).

• Были получены нижние оценки сложности для ограниченных моделей (схемы ограниченной глубины, монотонные схемы, коммуникационная сложность).

• Однако остаются нерешенными центральные задачи, прежде всего, получение нижних оценок для общих моделей вычислений. Что делать? Во-первых, не огорчаться: в науке должны быть важные нерешенные проблемы. Во-вторых, надо заниматься фундаментальными вопросами, а не идти напролом. (Скажем, полет на Луну стал возможен в результате постепенного развития науки и техники.) Но вопросы должны быть действительно фундаментальными: не надо залезать на деревья, считая, что это хоть немного приближает нас к цели…

Она была присуждена греческому специалисту по TCS Христосу Пападимитриу (Christos H. Papadimitriou). В своей лекции он говорил, что на границе математики, информатики и экономики возникают интересные задачи, которые могут иметь практическое значение в связи с развитием Интернета. Удивительно, если вдуматься, что огромный конгломерат людей и организаций с самыми разными целями и интересами умудряется худо-бедно функционировать, не имея ни единого центра, ни общепринятых экономических механизмов ⁴. Возникающий в связи с этим вопрос: каковы должны быть механизмы, чтобы эгоистические цели участников совпадали с общими (или не сильно противоречили им)? Вот самый простой пример родственной задачи: на аукционах не всегда выгодно называть свою предельную цену (вдруг других претендентов не найдется?). Но если изменить правила и считать, что победитель аукциона (назвавший максимальную цену) получает товар, но платит за него столько, каково было следующее по стоимости предложение, то стимулов скрывать свои возможности не будет (этот пример хорошо известен в экономике под названием «Аукционы Викри» [«Vickrey auctions»]).

Интересны (особенно для российских граждан) были рассказы Пападимитриу о себе. Когда он был студентом, греческое правительство плохо обращалось («tortured a bit», как он выразился) со своими гражданами. Пришлось бежать из страны. Пападимитриу поступил в американскую аспирантуру (чему режим черных полковников не препятствовал, в отличие от некоторых других), но продолжал надеяться на развитие теоретической информатики в Греции (и, как политически некорректно добавил он, «превращение Греции во второй Израиль Средиземноморья» - имея в виду, что многие известные специалисты по TCS, в том числе значительная часть участников конференции, работают в Израиле).

Курт Гёдель (Kurt Gцdel) - великий австрийский математик и логик, премия его имени присуждается с 1993 года совместно двумя организациями: SIGACT ⁵ ACM и EATCS (European Association for Theoretical Computer Science). Ею награждают за важнейшие статьи по теоретической информатике. В этом году премию получали сразу девять человек: Санджив Арора (Sanjeev Arora), Уриель Файге (Uriel Feige), Шафи Голдвассер (Shafi Goldwasser), Карстен Лунд (Carsten Lund), Ласло Ловаш (Laszlo Lovбsz), Ражив Мотвани (Rajeev Motwani), Шмуел Сафра (Shmuel Safra), Mэдху Судан (Madhu Sudan), Марио Сегеди (Mario Szegedy). Как отметил выступавший от их имени Уриель Файге, премия присуждена не столько людям, сколько некоторому кругу идей и понятий: вероятностно проверяемым доказательствам (Probabilistically Checkable Proofs, PCP) и получаемым с их помощью оценкам сложности аппроксимационных задач.

Предыстория такова. В 1993 году премию Геделя получили Ласло Бабаи (Lбszlу Babai), Шломо Моран (Shlomo Moran), Сильвио Микэли (Silvio Micali) и Чарльз Раков (Charles Rackoff) за «интерактивные доказательства». Традиционно «доказательство» означало «рассуждение, которое убеждает нас настолько, что мы готовы с его помощью убеждать других». Интерактивное доказательство - уже не рассуждение-монолог, а диалог доказывающего и проверяющего доказательство (проверяющий может пользоваться датчиком случайных чисел). Но теперь проверяющий не может пересказать доказательство третьему лицу (ведь вопросы-то могут быть заданы другие!). Оказалось, что всему этому можно придать точный математический смысл и доказать нетривиальные результаты. Дальнейшее развитие этого круга идей и привело к концепции PCP.

Борис Абрамович Трахтенброт - один из зачинателей TCS в СССР, ныне работает в Израиле. В программу конференции - в честь восьмидесятилетия Трахтенброта - был включен его доклад о правильном подходе к математическому моделированию гибридных (цифро-аналоговых) систем.

[i40738]