КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер проекта 20-11-20203

НазваниеВопросы сложности в теоретической информатике

Руководитель Верещагин Николай Константинович, Доктор физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Национальный исследовательский университет "Высшая школа экономики" , г Москва

Конкурс №45 - Конкурс 2020 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-114 - Дискретная математика и математическая кибернетика

Ключевые слова алгоритмическая теория информации, позиционные игры, колмогоровская сложность, сложность вычислений, коммуникационная сложность, булевы схемы, формальные языки, конечные автоматы

Код ГРНТИ27.41.41

---

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

---

Аннотация
Проект направлен на исследования сложностных аспектов в ряде разделов теоретической информатики. Вопросы сложности вычислений начали развиваться вслед за вопросами разрешимости еще в первой половине 20-го века. Новую жизнь это направление приобрело в 70-х годах в связи с появлением теории NP-полноты и развитием структурной сложности вычислений. В настоящее время теоретическая информатика является богатой областью с множеством тесно переплетающихся разделов. Вопросы сложности пронизывают все эти разделы и во многих случаях играют определяющую роль. Структурная сложность является фундаментом и основой всей современной теории сложности вычислений. Быстрое развитие этой области началось с появления теории NP-полноты в 70-х годах, и с тех пор в этой области была получена масса интересных и красивых результатов, благодаря которым сформировалась богатая картина сложностных классов. Эта область безусловно по-прежнему остается актуальной. С ней связаны ключевые проблемы в теоретической информатике, такие как вопрос о равенстве сложностных классов P и NP. Вопрос об определениях количества взаимной информации в двух бесконечных последовательностях был поднят в работе Л. Левина 1974 года. Согласно Левину, правильное определение должно обобщать определение количества взаимной информации в конечных словах и обладать двумя законами сохранения: для любой фиксированной последовательности количество взаимной информации в этой последовательности и любой другой не должно увеличиваться при алгоритмических и вероятностных преобразованиях этой второй последовательностей. Важным вопросом остается нахождение хорошего определения. Одной из важных задач современной теории сложности вычисления является нахождение полиномиального детерминированного алгоритма для проблемы равенства нулю многочлена. Нахождение неизвестных ранее частных случаев, для которых эта задача имеет полиномиальное детерминированное решение является актуальной проблемой. Классическим направлением теоретической информатики, тесно связанным со сложностью, является изучение сложности вычисления булевых функций в различных моделях вычислений комбинаторного вида. Одной из основных таких моделей являются булевы схемы. Исследования этой модели сильно продвинулись в 80-е годы в связи с проблемой о равенстве сложностных классов P и NP, но и сейчас эта и другие подобные модели остаются актуальными и востребованными. В рамках проекта планируется уделить внимание как самим булевым схемам, так и более базовым моделям, таким как разрешающие деревья. Коммуникационная сложность является достаточно молодым разделом теории сложности вычислений, появившимся лишь в конце 70-х годов. Тем не менее сейчас этот раздел является одним из ключевых. Результаты из коммуникационной сложности часто используются в других разделах сложности вычислений для получения нижних оценок. Сжатие информации без потерь — область, важная как для прикладных, так и для теоретических исследований. В последние годы большое распространение также получили распределенные вычисления и сжатие с участием нескольких вычислительных устройств. Не так давно Мариус Зиманд построил вероятностный полиномиальный алгоритм, позволяющий сжимать слова минимального возможного значения: колмогоровской сложности. Этот результат обобщает теорему Шеннона о кодировании источника и теорему Слепяна-Вольфа. Мы планируем исследовать, какие следствия вытекают из этой теоремы для колмогоровской сложности с ограничением на ресурсы и для распределенного сжатия с несколькими отправителями. Изучение случайных графов является обширным и глубоко разработанным разделом теории графов. В этой области исследуются типичные свойства случайно выбранных графов. Например, известно, что большинство графов ограниченной степени удовлетворяют определению экспандера, что влечет важные комбинаторные свойства — большой коэффициент вершинного расширения, сильную связность, свойство быстрого перемешивания, и т.д. Экспандеры имеют многочисленные применения в информатике и теории кодирования. В 2017 году была описана сложность задачи удовлетворения ограничениям, то есть для любого языка ограничений (множества предикатов) на конечном множестве описана сложность проверки истинности замкнутой формулы первого порядка с кванторами существования, конъюнкциями и предикатами из этого множества. Актуальной при этом остается кванторная задача удовлетворения ограничениям (QCSP). Равновесие Нэша — одна из основных игровых концепций при моделировании экономических, политических и военных конфликтов, отражающая стабильность, т.е., отсутствие у участников мотивации отступать от принятых договорённостей (стратегий). Важным частным случаем является равновесие Нэша в чистых стратегиях. Равновесия в чистых стационарных (позиционных) стратегиях особенно просты с алгоритмической точки зрения и имеют дополнительные преимущества, связанные с тем, что нивелируется роль случая и времени. Таким образом, важно выяснить и научиться эффективно проверять условия существования таких равновесий, что позволит избежать более сложных методов, связанных с рандомизацией и динамикой. Теория конечных автоматов является классическим направлением теории сложности, с которого начинаются многие учебники. Несмотря на заметный возраст этой области, очень многие вопросы в ней остаются открытыми. В рамках проекта планируется исследовать вопросы сложности автоматов с дополнительными структурами данных.

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---