В Санкт-Петербурге есть замечательное место, где из программистов делают ученых — теоретиков Computer Science. Это Академический Университет Российской Академии Наук (АУ РАН).
На тот момент, когда я поступила на Теоретическое Отделение кафедры Математических и Информационных Технологий АУ, отделение имело только один выпуск, состоящий из двух человек. Сейчас Академический Университет уже заработал себя прекрасное имя. Его выпускники работают в ведущих компаниях города, он принимает студентов из других городов, обеспечивая их жильем, а платное отделение стоит всего-навсего 10 тыс. рублей в семестр.
Но я хочу рассказать, на своем примере, какие интересные и глубокие проблемы можно исследовать и сколько интересного узнать, если вы станете студентом теоретического отделения.
Моя исследовательская работа в АУ
На теоретической кафедре АУ обязательным является проведение серьезного исследования для написания магистерской работы. Руководители очень стараются, чтобы у вас при этом появилась публикация — что уже очень заманчиво.
Моей работой руководил Дмитрий Михайлович Ицыксон (ПОМИ РАН) и посвящена она была исследованию оптимальных алгоритмов. Это очень интересная тема, а замечательна она еще и тем, что ее легко объяснить, и я сейчас попробую это сделать.
Мотивация
Давайте посмотрим на какую-нибудь NP-полную задачу, например, на язык выполнимых формул. Будем рассматривать алгоритмы, которые останавливаются на любой формуле и возвращают в качестве ответа один бит — является формула выполнимой или нет. Вот уже 40 лет стоит вопрос, есть ли среди этого множества алгоритмов полиномиальный, и никто до сих пор не смог на него ответить. Однако, мы можем задаться другим, возможно, более простым вопросом, существует ли у этой задачи оптимальный алгоритм — алгоритм, который работает быстрее всех остальных с точностью до полинома (поскольку нас интересует только полиномиальность алгоритмов). Допустим, такой оптимальный алгоритм существует (назовем его A), тогда NP не равно P в том и только в том случае, если A не является полиномиальным. Это уже что-то, поскольку нам надо доказать неполиномиальность одного конкретного алгоритма, вместо того, чтобы делать это для всех возможных алгоритмов, решающих нашу задачу.
Посмотрим на другой пример — на co-NP полную задачу, например, язык тавтологий (всюду верных формул). Существует большое количество систем доказательств для тавтологий: метод резолюций, система секущих плоскостей, системы Фреге и др. Вопрос о существовании системы доказательств, которая имела бы доказательства полиномиального размера эквивалентен открытому вопросу о равенстве классов NP и co-NP. На самом деле, удивительно, как много людей занимается сравнением конкретных систем доказательств и нахождением нижних оценок для них. Было бы здорово иметь оптимальную систему доказательств, тогда нам достаточно было бы изучать ее одну.
Итак, оба эти вопроса послужили мотивацией к изучению оптимальных алгоритмов для моей магистерской диссертации и мы получили действительно кое-что интересное в этом направлении.
Предыдущие исследования
Годом раньше Д.Ицыксон и Э.А.Гирш доказали существование оптимального эвристического вероятностного полуалгоритма для любого перечислимого языка, где
- полуалгоритм — половинка разрешающего алгоритма — алгоритм, который отвечает 1 на входах из языка и не останавливается на других входах
- вероятностный — алгоритм имеет доступ к случайным битам (может подкидывать честную монетку)
- эвристический — алгоритм может делать небольшую (ограниченную) ошибку, причем эта ошибка может быть сделана сколь угодно маленькой за счет увеличения времени работы.
Естественно, мы бы хотели построить оптимальный алгоритм для более слабой модели вычислений. Во-первых, мы хотели бы избавиться от ошибки, которую дает алгоритм, а во-вторых, сделать его не вероятностным, а детерминированным. Последнее преобразование называется дерандомизацией, и существуют более или менее стандартные методы для этого. Мне предлагалось попробовать претворить их в жизнь.
Результаты
Вместо того, чтобы использовать случайные биты, надо постараться извлечь случайность (энтропию) из входа (поскольку больше неоткуда). Это можно сделать с помощью двудольного «перемешивающего» графа (что-то вроде lookup table), где в левой доле мы будем индексироваться по входу, а множество смежных вершин из правой доли будет давать нам множество псевдослучайных битов.
После первой попытки сформулировать необходимые условия на граф, мы поняли, что сделать это в общем случае не представляется возможным, поэтому мы решили рассматривать более простой случай — язык множества образов инъективной функции, увеличивающей свой вход на один бит. Здесь у читателя (если есть читатели, которые сюда добрались) должно появиться законное возмущение: «кому же интересны такие языки»? Однако, допустим, мы интересуемся псевдослучайным генератором (существование доказуемо надежных инъективных генераторов, увеличивающих свой вход на один бит, является открытым вопросом). Тогда мы получим оптимальный алгоритм, который будет говорить: «правда ли, что данное (ему) число было порождено нашим генератором»? Если этот оптимальный алгоритм окажется полиномиальным, мы «сломаем» генератор, т.е. мы отличим числа, которые он порождает от действительно случайных! Это было бы действительно очень здорово, потому что мы бы нашли атаки на практически все существующие криптосистемы.
Итак, в этом случае, дерандомизация нам удалась и более того, мы построили не только оптимальный эвристический полуалгоритм, но дополнили его до полного алгоритма.
Закончились мои изыскания статьей и большим желанием не покидать замечательную область теоретической информатики, где еще очень много открытых вопросов и нерешенных проблем.
Пять причин, чтобы пойти в магистратуру АУ...
… если вы хотите заниматься теоретической информатикой:
- АУ единственное место в Питере и одно из немногих в России, где вы можете посвятить себя изучению теоретической информатики.
- В АУ работают энергичные и бесспорно талантливые ученые.
- В АУ студенты могут влиять на программу обучения и выбирать часть курсов по своему усмотрению.
- АУ спонсирует поездки на школы, зарубежные в том числе.
- В АУ вы найдете бесплатный кофе из чудесной эспрессо машины! (дабы было что перерабатывать в теоремы).
Что я делаю после окончания АУ?
Я продолжаю заниматься теоретической информатикой в Стэнфорде. В предыдущей четверти я занималась вычислениями на зашифрованных данных с Dan Boneh, а сейчас буду заниматься схемной сложностью с Ryan Williams.
Так что, мой совет — дерзайте, это стоит попробовать! Заявление можно подать прямо сейчас.
Автор: valerini
