Предзащита докторской диссертации Михаила Рыбакова

23 апреля на логическом семинаре лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ) прошла предзащита докторской диссертации Михаила Рыбакова «Моделирование логических систем средствами их фрагментов».

Аннотация

Проведенное исследование связано с выразительностью языков, логик и теорий, и прежде всего с алгоритмической выразительностью (в том числе вычислительной сложностью) определенных их фрагментов.

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

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

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

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