Сложность в среднем и диофантова сложность

Вот уже почти два года я являюсь студентом CS центра. Все это время под руководством Эдуарда Алексеевича Гирша я занимался теорией сложности: я изучал сложность в среднем и диофантову сложность.

Теория сложности — это наука, которая изучает нижние оценки на сложность алгоритмов (время работы, необходимый размер памяти и т.д.) для самых разных вычислительных моделей: детерминированных алгоритмов, вероятностных алгоритмов или даже квантовых вычислений. Примером задачи, рассматриваемой в рамках данной науки, может служить следующая проблема: дана формула от $n$ переменных, требуется определить, можно ли за $p(n)$ шагов узнать, выполнима она или нет (где $p$ — многочлен). Или другая: дан граф на $n$ вершинах и требуется за $p(n)$ шагов проверить, есть ли в нем клика размера $k$.

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

Что касается меня, то я, как и Ваня Михайлин, занимаюсь оценками схемной сложности, но я рассматриваю более сложные функции: функции, задаваемые вероятностными протоколами Мерлина-Артура, при этом меня интересует не классическая сложность, а сложность в среднем. Мне удалось построить такое семейство языков из класса МА, что для любого многочлена в нём найдется язык, имеющий большую сложность. Об этой работе можно прочитать в моей статье, опубликованной в ECCC. По результатам исследований я также сделал докладна семинаре в Computer Science клубе. Диофантова сложность изучает сложность вычислений намного более необычной модели, она интересуется следующим вопросом: правда ли, что в случае недетерминированных вычислений машину Тьюринга можно заменить на диофантово уравнение. Мне удалось показать, что классические и диофантовы вычисления схожи и что иерархии, построенные на их основе, практически совпадают. Об этом также написана статья, опубликованная в журнале Записки научных семинаров ПОМИ (перевод на английский: Journal of Mathematical Sciences, Springer).