16 ноября 2023 г. И. Н. Пономаренко (ПОМИ). Размерность Вейсфейлера-Лемана и проблема изоморфизма для конкретных категорий.

В докладе будет рассматриваться проблема изоморфизма для двух видов конкретных категорий: конечных групп и конечных графов. Сама проблема состоит в нахождении наиболее эффективного алгоритма, проверяющего изоморфизм для любых двух данных объектов рассматриваемой категории. Главным открытым вопросом здесь остается вопрос о существовании алгоритма, время работы которого не превосходит полинома от размера объектов, проверяемых на изоморфизм. Доказательство несуществования такого алгоритма привело бы к отрицательному ответу на проблему миллениума P=NP.

Размерность Вейсфейлера-Лемана (введенную для групп и графов в последнее десятилетие) можно рассматривать как меру сложности данного объекта с точки зрения проблемы изоморфизма. В рамках доклада будут представлены эквивалентные определения этой размерности, возникающие в математической логике (логика первого порядка со считающими кванторами), в алгебре (кольца Шура) и в анализе алгоритмов (многомерный алгоритм Вейсфейлера-Лемана). Мы обсудим ряд последних результатов, связанных с размерностью Вейсфейлера-Лемана, и сформулируем некоторые открытые вопросы.

Предыдущие заседания семинара: список докладов.