В ноябре этого года обладателем премии Дональда Кнута, одного из наиболее престижных призов в области информатики (computer science), стал Леонид Левин.
Ученик Колмогорова Леонид Левин – пожалуй, самый известный ученый в этой области из родившихся в Советском Союзе. В 1971 году одновременно с американским информатиком Стивеном Куком (и независимо от него) Левин описал особый класс сложных алгоритмических задач – NP-полные задачи, в который входят очень многие практический проблемы, например, известная «задача коммивояжера» (найти кратчайший способ объехать некий набор городов и вернуться в исходный). Кроме того, Левин сформулировал вопрос о равенстве классов P и NP: можно ли найти для решения задач класса NP достаточно хороший – выполняемый за полиномиальное время – алгоритм? Этот вопрос до сих пор остается открытым и входит в число «задач тысячелетия» – семи, если считать решенную Григорием Перельманом гипотезу Пуанкаре, сложнейших математических проблем, за решение каждой из которых Институт Клэя назначил премию в миллион долларов.
В начале 70-х свободомыслие Левина привело к его конфликту с комсомольскими функционерами Московского университета, что, несмотря на поддержку Колмогорова, помешало Левину защитить диссертацию в СССР. Это стало одной из причин эмиграции Леонида Левина в США в 1978 году (некоторые подробности можно найти здесь). В настоящее время Левин является профессором Бостонского университета.
Мы связались с Леонидом по электронной почте и поговорили о сложности, будущем и демократии.
Премия Дональда Кнута была вручена вам, в каком-то смысле, по совокупности заслуг: за 40 лет исследований и множество замечательных результатов. Самый знаменитый из них – работы, связанные с NP-полнотой, не так ли?
Я не думаю, что это самые важные мои работы. Я намного больше ценю другие, связанные с общими концепциями: информация, случайность, сложность и.т.п.
Любопытно, что вы не считаете работы про NP самыми важными,
при том, что они не просто наиболее известны, но и легли в основание целых научных областей и стали поводом для огромного количества исследований.
Понятия универсальности вообще и NP-универсальности в частности, конечно, очень важны. Но моя заслуга в них невелика. После классических работ Тьюринга и других эти понятия лежали на поверхности.
Каков, кстати, ваш личный прогноз: P равно NP?
No idea! (абсолютно ничего не знаю).
Одна из тем вашей работы связана с алгоритмической проверкой
доказательств. За последние несколько десятилетий мы видели много примеров появления чрезвычайно сложных доказательств математических теорем. Часть из них использовали компьютерные вычисления (как проблема четырех красок), часть – нет (как доказательство большой теоремы Ферма), но во всех случаях в конечном итоге доказательства были малодоступны даже для специалистов. Вам не кажется, что в математике происходит кризис переусложнения?
«Переусложнение» – «loaded word», это означает, что сложность
неоправданна, что, конечно, смешно: пусть попробуют доказать проще.
Со временем многие сложные доказательства упрощаются, но не все и не без длительных усилий. Кроме того, сложность идей часто просто означает их непривычность. Привычки меняются, и с ними – наше представление о том, что сложно. Другой аспект – это то, что сложность мешает популярности. Давление в сторону популярности – это одна из многих безумных проблем демократии: Сократ был отравлен афинскими демократами за независимость и непопулярность.
Да, но проблема не только в популярности, но и в независимой проверке, обеспечивающей легитимность. Вот несколько месяцев назад японец Мочидзуки объявил о решении старой и очень сложной задачи из теории чисел, ABC-проблемы, но его доказательство до сих пор никому не удалось понять. Можно ли считать вопрос закрытым, пока проверка не состоялась?
Это временная проблема. Если Мочидзуки смог доказать (и правильно притом) ABC-гипотезу, значит, у него была интуиция, которая упрощала эту проблему. Он не смог еще передать коллегам эту интуицию, но со временем кто-то сделает это за него.
А может быть, проверять доказательства при помощи компьютера, алгоритмически – это и есть идеальный путь? Понятно, что это потребует со стороны ученых соблюдать формальные приемы, при записи доказательств, но, по крайней мере, не будет сомнений, что то, что доказано, – действительно доказано?
Алгоритмическая проверка, конечно, будет расширяться. Но как далеко она уйдет в то небольшое время, которое осталось нам, людям, как центральной интеллектуальной силе цивилизации? Заставить математиков выписывать мельчайшие детали невозможно. Компьютеры когда-нибудь научатся делать это за них, но много ли времени пройдет после этого, пока компьютеры научаться делать за них ВСЁ?
Пока что, я думаю, алгоритмическая проверка важна не столько для математических теорем, сколько для более рутинных процессов: огромных вычислений, баз данных и пр. Голографическая форма доказательств (Они входят в сферу научных интересов Левина. – Прим. ред.) открывает принципиальную возможность мгновенно проверять правильность таких архивов абсолютно любого размера. Однако для практической реализации этих методов нужно еще преодолеть много технических трудностей.
Расскажите, что такое голографическая форма доказательств? И о каких технических препятствиях идет речь?
Это трудно объяснить. Отрезав кусок фотографии, вы потеряете ухо или глаз. Голограмма же выглядит, как окно, за которым виден образ. Отрежeте кусок – окно станет меньше, но все равно, двигая головой, можно видеть любую часть образа, хотя и менее четко. Голографическое доказательство в любой своей части несет информацию обо всем оригинале. Существенную ошибку такой голограммы нельзя скрыть: ее видно почти в любом крохотном кусочке. Но пока что эти голограммы несколько длиннее оригиналов, что непрактично, если оригинал сам огромен.
Вообще говоря, многие математики с подозрением и неудовольствием относятся к использованию компьютеров в таком чистом жанре, как доказательство.
Компьютерная цивилизация еще в зачаточной стадии, и вживание в нее требует времени. Я, например, все еще боюсь почти всей новой электроники. Даже e-mail и editor, которыми я сейчас пользуюсь для этого интервью, – те же, что я использовал треть века назад. Чтобы компьютеры могли просто проверить доказательство, придуманное математиком, автор должен прежде всего изложить все мельчайшие детали, чего никто делать не хочет. Когда математики сами проверяют доказательства своих коллег, они угадывают эти детали, т.е., по существу, делают рутинную часть доказательств сами. Так что проблема не в проверке доказательств компьютером, а в отыскании им самим рутинных (для математиков) доказательств. Это гораздо более сложная проблема. Она, конечно, будет решена, но не быстро.
Есть ощущение, что мир стал меняться все быстрее: особенно это заметно по нашему обращению с информацией. Вы согласны?
Конечно. Цивилизация переходит в новую стадию. Мало что переживет столетие.
Какова эта новая стадия?
Революции в хранении, обработке и передаче информации никогда не оставляли мир каким он был. Возникновение информационного механизма ДНК/РНК породило жизнь какой мы ее знаем. Эволюция речи породила разум. Появление письма породило цивилизацию. Бумага и печать сделали письмо общедоступным, и мир перешел в технологическую фазу. Нет сомнений в том, что компьютерные технологии приведут к не менее радикальным следствиям, но было бы глупо мне, с моим хлипким воображением, пытаться их предсказать.
И что именно не переживет столетия – идеи, привычки, традиции, технологии? А что, наоборот, переживет?
Мало что переживет. Обычно говорят, что человеческая глупость переживет все, но я даже в этом не уверен.
Вы говорите о начале нового цивилизационного этапа и об изменении
значения компьютеров, но ни разу не упомянули искусственный интеллект. Что вы думаете об исследованиях в области искусственного интеллекта и о популярных в последнее время когнитивных науках – науках о сознании?
Я абсолютно ничего не могу сказать об «искусственном интеллекте» и «когнитивных науках». Там люди пишут бог знает что.
Вы считаете это все шарлатанством или вам просто неинтересно?
Я бы не назвал это шарлатанством, скорее сомнительной рекламой.
На вашей странице опубликовано небольшое эссе о демократии. Оно достаточно критично, по крайней мере в том, что касается всеобщего избирательного права и перераспределения благ. Вы действительно против демократии? Или речь конкретно о демократической партии США? Что вы думаете о либерализме?
Я, разумеется, против подавления или эксплуатации меньшинства большинством, как и большинства меньшинством: это не связано со степенью концентрации власти. По Аристотелевской классификации систем правления, коррупция вырождает монархию в тиранию, аристократию – в олигархию, а республику – в демократию. Любой носитель власти, включая большинство, должен быть ограничен неподвластными ему принципами, охраняющими безвластных. В Америке эту роль играют, все еще сильные, моральные принципы пилигримов. Это лучше, чем принцип Дарвина: военный или экономический коллапс паразитических систем.
А вы следите за положением дел в современной России? Что думаете о происходящем?
Карамзин ответил на этот вопрос одним словом: «Воруют». Я не думаю, что с тех пор что-то изменилось в этом отношении.
Вам не кажется, что в нынешней России появляются признаки тоталитаризма, которые могут вернуть страну в то состояние, когда возможны ситуации, подобные той, которая привела к вашей эмиграции?
В России всегда были признаки (и не только признаки) и тоталитаризма, и дикой анархии. Цивилизацию нельзя создать просто доброй волей, как и недостаточно простого желания, чтобы переделать самокат в Мерседес. Когда-то было найдено решение: «Земля наша велика и обильна, а наряда в ней нет; приходите княжить и володети нами». Но теперь люди слишком горды для этого.
Неприятные вещи происходят в вашей альма-матер, школе Колмогорова. Следите ли вы за этой ситуацией?
Я знаю понаслышке. Конечно, положение в школе Колмогорова, в МГУ в целом и в Российской науке вообще очень печально.
Печально, потому что «воруют»? Или есть и другие причины?
Причина в том, что научные структуры по необходимости консервативны, и исправить гнилые структуры невозможно. Германия полностью расформировала восточногерманские научные структуры и создала новые на основе западных. У России «западного» района нет. Но у нее есть другой ресурс – огромная диаспора. Привлечь ее к возрождению (бывшего колоссальным) научного потенциала России будет стоить невероятных денег. Но возрождение науки – это единственный шанс России, ее билет в будущее...
Вы можете себе хотя бы представить собственное возвращение в Россию?
Не могу. Для этого я должен там снова родиться. Или в Америке демократия должна полностью победить республику.
А что должно случиться, чтобы талантливые люди хотя бы перестали уезжать, ведь этот процесс не прекращается?
В XIX веке Россия имела (кроме снега) два неисчерпаемых ресурса: зерно и территорию. Коммунисты зерно исчерпали, но лишенные доступа к экономической деятельности люди ринулись в науку. (Территория, потеряв стратегическое значение, приобрела экономическое, как источник горючего.) Теперь огромный научный потенциал России почти утерян. Моральный не приобретен. Углеводороды все еще в цене, но надолго ли? Так что я пессимист.
Как насчет Сколково?
Я ничего про это не знаю, надо спросить у Карамзина.
Ученик Колмогорова Леонид Левин – пожалуй, самый известный ученый в этой области из родившихся в Советском Союзе. В 1971 году одновременно с американским информатиком Стивеном Куком (и независимо от него) Левин описал особый класс сложных алгоритмических задач – NP-полные задачи, в который входят очень многие практический проблемы, например, известная «задача коммивояжера» (найти кратчайший способ объехать некий набор городов и вернуться в исходный). Кроме того, Левин сформулировал вопрос о равенстве классов P и NP: можно ли найти для решения задач класса NP достаточно хороший – выполняемый за полиномиальное время – алгоритм? Этот вопрос до сих пор остается открытым и входит в число «задач тысячелетия» – семи, если считать решенную Григорием Перельманом гипотезу Пуанкаре, сложнейших математических проблем, за решение каждой из которых Институт Клэя назначил премию в миллион долларов.
В начале 70-х свободомыслие Левина привело к его конфликту с комсомольскими функционерами Московского университета, что, несмотря на поддержку Колмогорова, помешало Левину защитить диссертацию в СССР. Это стало одной из причин эмиграции Леонида Левина в США в 1978 году (некоторые подробности можно найти здесь). В настоящее время Левин является профессором Бостонского университета.
Мы связались с Леонидом по электронной почте и поговорили о сложности, будущем и демократии.
Премия Дональда Кнута была вручена вам, в каком-то смысле, по совокупности заслуг: за 40 лет исследований и множество замечательных результатов. Самый знаменитый из них – работы, связанные с NP-полнотой, не так ли?
Я не думаю, что это самые важные мои работы. Я намного больше ценю другие, связанные с общими концепциями: информация, случайность, сложность и.т.п.
Любопытно, что вы не считаете работы про NP самыми важными,
при том, что они не просто наиболее известны, но и легли в основание целых научных областей и стали поводом для огромного количества исследований.
Понятия универсальности вообще и NP-универсальности в частности, конечно, очень важны. Но моя заслуга в них невелика. После классических работ Тьюринга и других эти понятия лежали на поверхности.
Каков, кстати, ваш личный прогноз: P равно NP?
No idea! (абсолютно ничего не знаю).
Одна из тем вашей работы связана с алгоритмической проверкой
доказательств. За последние несколько десятилетий мы видели много примеров появления чрезвычайно сложных доказательств математических теорем. Часть из них использовали компьютерные вычисления (как проблема четырех красок), часть – нет (как доказательство большой теоремы Ферма), но во всех случаях в конечном итоге доказательства были малодоступны даже для специалистов. Вам не кажется, что в математике происходит кризис переусложнения?
«Переусложнение» – «loaded word», это означает, что сложность
неоправданна, что, конечно, смешно: пусть попробуют доказать проще.
Со временем многие сложные доказательства упрощаются, но не все и не без длительных усилий. Кроме того, сложность идей часто просто означает их непривычность. Привычки меняются, и с ними – наше представление о том, что сложно. Другой аспект – это то, что сложность мешает популярности. Давление в сторону популярности – это одна из многих безумных проблем демократии: Сократ был отравлен афинскими демократами за независимость и непопулярность.
Да, но проблема не только в популярности, но и в независимой проверке, обеспечивающей легитимность. Вот несколько месяцев назад японец Мочидзуки объявил о решении старой и очень сложной задачи из теории чисел, ABC-проблемы, но его доказательство до сих пор никому не удалось понять. Можно ли считать вопрос закрытым, пока проверка не состоялась?
Это временная проблема. Если Мочидзуки смог доказать (и правильно притом) ABC-гипотезу, значит, у него была интуиция, которая упрощала эту проблему. Он не смог еще передать коллегам эту интуицию, но со временем кто-то сделает это за него.
А может быть, проверять доказательства при помощи компьютера, алгоритмически – это и есть идеальный путь? Понятно, что это потребует со стороны ученых соблюдать формальные приемы, при записи доказательств, но, по крайней мере, не будет сомнений, что то, что доказано, – действительно доказано?
Алгоритмическая проверка, конечно, будет расширяться. Но как далеко она уйдет в то небольшое время, которое осталось нам, людям, как центральной интеллектуальной силе цивилизации? Заставить математиков выписывать мельчайшие детали невозможно. Компьютеры когда-нибудь научатся делать это за них, но много ли времени пройдет после этого, пока компьютеры научаться делать за них ВСЁ?
Пока что, я думаю, алгоритмическая проверка важна не столько для математических теорем, сколько для более рутинных процессов: огромных вычислений, баз данных и пр. Голографическая форма доказательств (Они входят в сферу научных интересов Левина. – Прим. ред.) открывает принципиальную возможность мгновенно проверять правильность таких архивов абсолютно любого размера. Однако для практической реализации этих методов нужно еще преодолеть много технических трудностей.
Расскажите, что такое голографическая форма доказательств? И о каких технических препятствиях идет речь?
Это трудно объяснить. Отрезав кусок фотографии, вы потеряете ухо или глаз. Голограмма же выглядит, как окно, за которым виден образ. Отрежeте кусок – окно станет меньше, но все равно, двигая головой, можно видеть любую часть образа, хотя и менее четко. Голографическое доказательство в любой своей части несет информацию обо всем оригинале. Существенную ошибку такой голограммы нельзя скрыть: ее видно почти в любом крохотном кусочке. Но пока что эти голограммы несколько длиннее оригиналов, что непрактично, если оригинал сам огромен.
Вообще говоря, многие математики с подозрением и неудовольствием относятся к использованию компьютеров в таком чистом жанре, как доказательство.
Компьютерная цивилизация еще в зачаточной стадии, и вживание в нее требует времени. Я, например, все еще боюсь почти всей новой электроники. Даже e-mail и editor, которыми я сейчас пользуюсь для этого интервью, – те же, что я использовал треть века назад. Чтобы компьютеры могли просто проверить доказательство, придуманное математиком, автор должен прежде всего изложить все мельчайшие детали, чего никто делать не хочет. Когда математики сами проверяют доказательства своих коллег, они угадывают эти детали, т.е., по существу, делают рутинную часть доказательств сами. Так что проблема не в проверке доказательств компьютером, а в отыскании им самим рутинных (для математиков) доказательств. Это гораздо более сложная проблема. Она, конечно, будет решена, но не быстро.
Есть ощущение, что мир стал меняться все быстрее: особенно это заметно по нашему обращению с информацией. Вы согласны?
Конечно. Цивилизация переходит в новую стадию. Мало что переживет столетие.
Какова эта новая стадия?
Революции в хранении, обработке и передаче информации никогда не оставляли мир каким он был. Возникновение информационного механизма ДНК/РНК породило жизнь какой мы ее знаем. Эволюция речи породила разум. Появление письма породило цивилизацию. Бумага и печать сделали письмо общедоступным, и мир перешел в технологическую фазу. Нет сомнений в том, что компьютерные технологии приведут к не менее радикальным следствиям, но было бы глупо мне, с моим хлипким воображением, пытаться их предсказать.
И что именно не переживет столетия – идеи, привычки, традиции, технологии? А что, наоборот, переживет?
Мало что переживет. Обычно говорят, что человеческая глупость переживет все, но я даже в этом не уверен.
Вы говорите о начале нового цивилизационного этапа и об изменении
значения компьютеров, но ни разу не упомянули искусственный интеллект. Что вы думаете об исследованиях в области искусственного интеллекта и о популярных в последнее время когнитивных науках – науках о сознании?
Я абсолютно ничего не могу сказать об «искусственном интеллекте» и «когнитивных науках». Там люди пишут бог знает что.
Вы считаете это все шарлатанством или вам просто неинтересно?
Я бы не назвал это шарлатанством, скорее сомнительной рекламой.
На вашей странице опубликовано небольшое эссе о демократии. Оно достаточно критично, по крайней мере в том, что касается всеобщего избирательного права и перераспределения благ. Вы действительно против демократии? Или речь конкретно о демократической партии США? Что вы думаете о либерализме?
Я, разумеется, против подавления или эксплуатации меньшинства большинством, как и большинства меньшинством: это не связано со степенью концентрации власти. По Аристотелевской классификации систем правления, коррупция вырождает монархию в тиранию, аристократию – в олигархию, а республику – в демократию. Любой носитель власти, включая большинство, должен быть ограничен неподвластными ему принципами, охраняющими безвластных. В Америке эту роль играют, все еще сильные, моральные принципы пилигримов. Это лучше, чем принцип Дарвина: военный или экономический коллапс паразитических систем.
А вы следите за положением дел в современной России? Что думаете о происходящем?
Карамзин ответил на этот вопрос одним словом: «Воруют». Я не думаю, что с тех пор что-то изменилось в этом отношении.
Вам не кажется, что в нынешней России появляются признаки тоталитаризма, которые могут вернуть страну в то состояние, когда возможны ситуации, подобные той, которая привела к вашей эмиграции?
В России всегда были признаки (и не только признаки) и тоталитаризма, и дикой анархии. Цивилизацию нельзя создать просто доброй волей, как и недостаточно простого желания, чтобы переделать самокат в Мерседес. Когда-то было найдено решение: «Земля наша велика и обильна, а наряда в ней нет; приходите княжить и володети нами». Но теперь люди слишком горды для этого.
Неприятные вещи происходят в вашей альма-матер, школе Колмогорова. Следите ли вы за этой ситуацией?
Я знаю понаслышке. Конечно, положение в школе Колмогорова, в МГУ в целом и в Российской науке вообще очень печально.
Печально, потому что «воруют»? Или есть и другие причины?
Причина в том, что научные структуры по необходимости консервативны, и исправить гнилые структуры невозможно. Германия полностью расформировала восточногерманские научные структуры и создала новые на основе западных. У России «западного» района нет. Но у нее есть другой ресурс – огромная диаспора. Привлечь ее к возрождению (бывшего колоссальным) научного потенциала России будет стоить невероятных денег. Но возрождение науки – это единственный шанс России, ее билет в будущее...
Вы можете себе хотя бы представить собственное возвращение в Россию?
Не могу. Для этого я должен там снова родиться. Или в Америке демократия должна полностью победить республику.
А что должно случиться, чтобы талантливые люди хотя бы перестали уезжать, ведь этот процесс не прекращается?
В XIX веке Россия имела (кроме снега) два неисчерпаемых ресурса: зерно и территорию. Коммунисты зерно исчерпали, но лишенные доступа к экономической деятельности люди ринулись в науку. (Территория, потеряв стратегическое значение, приобрела экономическое, как источник горючего.) Теперь огромный научный потенциал России почти утерян. Моральный не приобретен. Углеводороды все еще в цене, но надолго ли? Так что я пессимист.
Как насчет Сколково?
Я ничего про это не знаю, надо спросить у Карамзина.
