Наука для всех. Российская Академия Наук. (ras_daily) wrote,
Наука для всех. Российская Академия Наук.
ras_daily

Categories:

А. А. Разборов, теория сложности вычислений

Сегодня я хочу рассказать вам о сотруднике Математического института им. В.А. Стеклова РАН Александре Александровиче Разборове. Вот его домашняя страница.

Александр Разборов работает в области, которая по-английски называется Theoretical Computer Science, а по-русски можно, видимо, сказать «теоретическая информатика», устоявшегося термина тут нет. Сегодня я попробую рассказать только о части его результатов, посвященных сложности вычислений. Рассказ будет очень неформальным.

На случай, если у меня ничего не выйдет, можно почитать научно-популярные тексты самого Разборова. Вот его статья для Компьютерры, вот статья для «Математического Просвещения», вот статья для сборника «Математические события XX века», вот лекция для Полит.ру, наконец, вот здесь можно посмотреть лекции Разборова для школьников.

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

Центральным вопросом в этой науке является вопрос о сложностных классах P и NP (он, например, входит в известный список «Задач тысячелетия» института Клэя). Класс P – это, грубо говоря, класс тех задач, которые мы умеем решать быстро, то есть тех, для которых есть быстрый алгоритм. Класс NP определяется сложнее, грубо говоря, это класс задач, для которых мы умеем быстро проверять правильность решения, если нам его кто-то дал. В следующем абзаце я попробую объяснить это на примере. Вопрос о P и NP, это вопрос о том, совпадают ли эти классы. Большинство ученых считают, что классы не совпадают, но ни доказать, ни опровергнуть этого мы не можем. Интересно, что от того, как решится этот вопрос, может сильно зависеть, в каком мире мы живем. Вот ссылка (English) на интересный обзор, в котором описано как будет устроен мир при разных вариантах ответа на этот вопрос. Коротко и огрубляя, если окажется, что P=NP, то, компьютеры смогут делать гораздо больше вещей, например, сами писать компьютерные программы по данному описанию программы или эффективно доказывать математические теоремы. С другой стороны, перестанет работать любая электронная персональная идентификация, и вместе с ней наш современный Интернет. Так что вопрос о P и NP является абсолютно фундаментальным, хотя возможно и очень трудным.

Попробуем пояснить проблему о P и NP на примере. Пусть у нас есть группа людей, некоторые из которых друг с другом враждуют и отказываются вообще быть рядом. Еще у нас есть два автобуса, на которых мы этих людей хотим куда-то отвезти. Мы хотим рассадить их по этим автобусам и вообще понять, можно ли это сделать. Заметим, что это можно сделать не всегда, скажем, если есть три человека, которые все попарно враждуют между собой, то ничего не выйдет.

Оказывается, что такая задача простая, ее можно решать очень быстро. Компьютер будет делать это за секунды, даже если людей у нас несколько тысяч (и речь идет о двух пароходах). Алгоритм будет примерно такой. Берем любого человека и сажаем в какой-нибудь автобус. После этого сажаем всех его врагов в другой автобус. Затем сажаем врагов каждого из них в первый автобус и так далее. Если в какой-то момент окажется, что какой-то человек должен сидеть и в том, и в том автобусе, то все пропало, и сделать с этим ничего нельзя – рассадить людей невозможно. Наконец, если мы рассадили какую-то часть людей и всех их врагов тоже, но люди на улице еще остались, снова берем любого, сажаем в любой автобус и продолжаем.

Таким образом, эту задачу мы умеем решать быстро. На самом деле она принадлежит классу P.

Теперь, что произойдет, если у нас будет не два, а три автобуса? Наш алгоритм прямо так работать не будет, ведь теперь для врагов какого-нибудь человека у нас есть два варианта, куда их можно посадить – два других автобуса, и нужно как-то перебирать варианты. Оказывается, что не только наш алгоритм перестает работать, но и сама задача становится гораздо труднее. Оказывается, что для такой задачи мы просто не знаем быстрого алгоритма (то есть, может быть он и есть, но никто его не знает) и если речь идет о тысячах людей, то компьютеру потребуются уже месяцы и годы, чтобы решить такую задачу. Зато, если нам кто-то скажет ответ к нашей задаче, то есть кто-то укажет нам конкретную рассадку людей по автобусам, то мы можем легко проверить, что она годится – надо просто для каждой пары враждующих проверить, что они сидят в разных автобусах. Компьютер снова может делать это быстро. Такие задачи и составляют класс NP: если нам кто-то представил решение мы можем быстро проверить, верно ли оно. Оказывается, что этот класс очень важный, в него входит масса полезных задач, и никто не знает, умеем ли мы их быстро решать, а не только проверять готовые решения.

После этого вступления я могу очень коротко рассказать о вкладе Александра Разборова в эту науку. На самом деле у Разборова масса результатов в этой области, но я сосредоточусь на двух.

Как я уже говорил, большинство ученых считают, что класс P не совпадает с классом NP, и пытаются доказывать именно это. Самые первые попытки (60-е и 70-е годы) решить этот вопрос опирались на идею диагонализации, восходящую к Кантору (конец 19-го века). Этот подход разбился о так называемую концепцию релятивизуемости. Грубо говоря, релятивизуемость означает, что любое доказательство какого-нибудь утверждения, основанное только на методе диагонализации, будет заодно доказывать и массу родственных утверждений (на самом деле за этим стоят очень красивые идеи, но о них нужно писать отдельно). И оказалось, что для утверждений “P=NP” и “P не равно NP” некоторые из родственных им утверждений попросту не верны. Следовательно, если мы хотим решать вопрос о P и NP, нам нужно что-то большее, чем просто диагонализация.

Следующей серьезной попыткой была идея перевести вопрос на язык так называемых логических схем. Я думаю, у меня уже нет возможности вдаваться в детали, так что скажу только, что процессор компьютера на самом деле представляет собой логическую схему. Подробнее о схемах можно почитать, например, здесь. После перевода на язык булевых схем, вопрос о  P и NP формально становится труднее, но поскольку схемы более структурированы, появляется больше возможностей подступиться к задаче. Базовой идеей этого подхода было рассматривать вместо произвольных логических схем схемы с некоторыми ограничениями. Возможно, для них получится решить задачу, и тогда у нас появятся методы. Потом мы будем эти методы развивать, постепенно избавляться от ограничений на схемы, и, в конце концов, решим нашу изначальную задачу. В этом направлении один из самых выдающихся и знаменитых результатов получен как раз Разборовым. Еще будучи аспирантом (в том же Математическом Институте РАН) в 1985 году он решил эту задачу для случая так называемых монотонных логических схем. Это очень важный и сильный класс схем, опять же я не могу здесь рассказать о них подробно.  Этот результат был настоящим прорывом, какое-то время люди были преисполнены оптимизма и считали, что вполне вероятно скоро будет решена и полная задача. Вскоре, впрочем, оказалось, что методы так просто на случай произвольных схем не обобщаются и дело застопорилось. Тем не менее, этот результат сильно изменил картину мира в этой науке и методы, полученные при его доказательстве, заняли свое важное место в этой области. За этот и смежные результаты Александр Разборов получил премию Неванлинны, одну из самых престижных премий в области Computer Science, вручаемую на Международном конгрессе математиков.

Теперь я могу рассказать о следующем результате, по сути, это продолжение истории. Итак, идея с использованием логических схем застопорилась, ближе к концу 80-х перестали появляться прорывные результаты в области. Здесь полезно сделать такое отступление. Вообще, на первый взгляд, самой естественной деятельностью в теории сложности вычислений выглядит получение новых алгоритмов. Действительно, при этом мы доказываем, что мы можем что-то сделать, мы доказываем что-то положительное. Если мы пытаемся доказать, что P не равно NP, то мы на самом деле пытаемся доказать нечто отрицательное. То есть, мы не получаем новых более быстрых алгоритмов, мы доказываем, что какие-то алгоритмы невозможны, то есть, что  чего-то сделать нельзя. На самом деле, эта деятельность не менее важна и очень тесно связана с первой (это я не смогу объяснить в двух словах, для этого нужен отдельный пост). Так вот, результат, о котором я хочу рассказать, добавляет еще один уровень отрицательности – это результат о том, что мы не умеем доказывать, что чего-то сделать нельзя. Более конкретно, Александр Разборов совместно со Стефаном Рудичем в 1994 году доказал, что все те методы, которые были разработаны учеными во время подхода к проблеме P и NP с помощью логических схем, то есть все те методы, которые у нас появились после диагонализации, все они не достаточны для доказательства того, что P не равно NP. Это означает, что для решения нашей задачи у нас пока просто нет методов и их сначала нужно найти. Этот результат полностью перевернул представление ученых обо всей области сложности вычислений и сильно сказался на ее дальнейшем развитии. За этот результат А. Разборов получил премию Геделя, другую очень престижную премию.

Я не могу рассказать в одном посте обо всех результатах Разборова. Упомяну только, что в последние годы в его кругу интересов большое место заняла область экстремальной комбинаторики. Очень огрубляя, эта область исследует числовые характеристики больших дискретных объектов. В этой науке Александр Разборов создал полноценную новую теорию, с помощью которой решил ряд давних проблем. За создание этой теории А. А. Разборов в этом году получил премию Роббинса, вручаемую Американским Математическим Обществом.


Владимир Подольский
Математический Институт им. В. А. Стеклова
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 4 comments