Квазиполиномиальная оценка Бабая
Ласло Бабаи (László Babai) предлагает квазиполиномиальный [трудоёмкость в худшем случае оценивается как exp(log^c n)] алгоритм для задачи поиска изоморфизма графов (см. также серию постов 1, 2, 3 и т.д. в журнале двух известных математиков, Dick Lipton & Ken Regan).
Как известно, эта задача относится к классу NP, однако, скорее всего, не является NP-полной, так как в этом случае было бы нарушено общепринятое предположение о бесконечности полиномиальной иерархии. Несмотря на это, до работы Ласло лучшая верхняя оценка сложности задачи GI была всего лишь субэкспоненциальной [порядка exp(sqrt(n log n))].
Результат пока не проверен полностью, предварительная версия статьи появился буквально на днях. Автор приглашает других математиков принять участие в работе. В серии ноябрьских докладов на семинаре Александра Александровича Разборова в Чикагском университете многие выдающиеся учёные мира уже приобщились к проблеме.
Теперь и всем нам доступна для просмотра видеозапись первой лекции. Ласло постарался в ней дать небольшое введение для неспециалистов (хотя кое-какие познания в математике, всё же, для понимания необходимы), поэтому все желающие могут прямо сейчас насладиться новостями с фронта мировой науки.
Впрочем, даже если ничего понять не удаётся, то можно просто насладиться каллиграфией и виртуозным искусством жонглирования шестью досками.
(конспект можно полистать здесь)
Как известно, эта задача относится к классу NP, однако, скорее всего, не является NP-полной, так как в этом случае было бы нарушено общепринятое предположение о бесконечности полиномиальной иерархии. Несмотря на это, до работы Ласло лучшая верхняя оценка сложности задачи GI была всего лишь субэкспоненциальной [порядка exp(sqrt(n log n))].
Результат пока не проверен полностью, предварительная версия статьи появился буквально на днях. Автор приглашает других математиков принять участие в работе. В серии ноябрьских докладов на семинаре Александра Александровича Разборова в Чикагском университете многие выдающиеся учёные мира уже приобщились к проблеме.
Теперь и всем нам доступна для просмотра видеозапись первой лекции. Ласло постарался в ней дать небольшое введение для неспециалистов (хотя кое-какие познания в математике, всё же, для понимания необходимы), поэтому все желающие могут прямо сейчас насладиться новостями с фронта мировой науки.
Впрочем, даже если ничего понять не удаётся, то можно просто насладиться каллиграфией и виртуозным искусством жонглирования шестью досками.
(конспект можно полистать здесь)
Click to view