Опубліковано швидкий алгоритм для задачі ізоморфізму графів


Ці два графа є изоморфными

Математик Ласло Бабай (László Babai) з факультету комп'ютерних наук і математики Чиказького університету представив новий швидкий алгоритм для рішення задачі ізоморфізму графів — однієї з фундаментальних проблем теорії складності обчислень. Алгоритм призводить проблему дуже близько до класу P. думку деяких фахівців, це один із самих значних результатів у галузі теоретичної інформатики за десятиліття, якщо не за кілька десятиліть.

Про створення алгоритму Ласло оголосив місяць тому. За його словами, алгоритм значно ефективніше, ніж найкращий з існуючих, який був рекордсменом більше тридцяти років: його розробив нині професор Юджин Люкс у 1983 році, той вирішував завдання за субэкспоненциальное час.

Ласло Бабаю, судячи з усього, вдалося практично звести проблему до задачі класу P: його алгоритм заявлений як обчислюваний в квазі-полиномиальное час.

11 грудня 2015 року стаття з описом нового алгоритму нарешті опубліковано у відкритому доступі, а також відправлена в Асоціації з обчислювальної техніки. Офіційна презентація алголритма відбудеться на 48-му симпозіумі з теорії обчислень.

Протягом кількох десятиліть проблема ізоморфізму графів мала особливий статус в теорії складності обчислень. У той час як сотні інших завдань смиренно піддавалися класифікації по класу P або класу NP, проблему ізоморфізму графів ніяк не могли однозначно класифікувати. Вона здавалася складніше, ніж легкі завдання і легше, ніж складні, займаючи унікальне положення ніби між двома класами завдань. Це одна з двох знаменитих завдань у цій дивній проміжної області, говорить Скотт Ааронсон (Scott Aaronson), математик з Массачусетського технологічного інституту. Тепер, за його словами «схоже, що одна з двох здалася».

Друга загальновідома завдання з «сірої» області — факторизація цілих чисел.

Завдання ізоморфізму графів сама по собі виглядає просто: потрібно визначити, є два графа изоморфными, тобто можна простим пересуванням вершин трансформувати один граф в інший, зберігаючи зв'язку між вершинами. От і все. Незважаючи на уявну простоту, це завдання важко вирішити, тому що навіть маленькі графи можуть приймати безліч різноманітних форм.


Ласло Бабай представляє свій алгоритм для рішення задачі ізоморфізму графів 10 листопада 2015 року в Чиказькому університеті

Алгоритм Ласло Бабая працює шляхом віртуального «фарбування» вершин графа. Спочатку випадковим чином вибираються кілька вершин, вони забарвлюються в різні кольори. Потім вибираються кілька вершин у другій графі, імовірно відповідних вершин з першого графа, їм присвоюються ті ж кольори. Зрештою, перебираються всі варіанти. Після початкового вибору алгоритм забарвлює на обох графах імовірно ізоморфні вершини, суміжні з спочатку обраними, в інші кольори до тих пір, поки не залишається зв'язків між вершинами.

Якщо алгоритм Бабая пройде перевірку колег, то це найзначніше відкриття в даному розділі математики за останній час. «До його оголошення навряд чи хтось, крім, може бути, його самого, припускав появу такого результату в найближчі десять років, якщо взагалі коли-небудь», — говорить Джошуа Грочоу (Joshua Grochow) з інституту Санта-Фе.

За останні кілька тижнів Бабай дав кілька лекцій з викладенням свого алгоритму. Відеозапис першої лекції від 10 листопада представлена нижче.



Завдання ізоморфізму графів вважається «універсальної», тобто до неї можна звести будь-яку проблему, де ставиться питання про изоморфизме комбінаторних структур. Зазвичай така «універсальність» властива завдань класу NP. У той же час завдання ізоморфізму графів демонструвала одну дивну властивість, якого немає ні в одній NP-повної задачі: проходження «сліпого тесту» (протокол Артура-Мерліна).

У 2012 році неформальне опитування учених у галузі теоретичної інформатики дав такий результат: 14 з них висловилися, що проблема ізоморфізму графів належить до класу P, а шестеро сказали, що не належить. До оголошення Ласло Бабая мало хто думав, що завдання вирішать коли-небудь найближчим часом. «Я думав, що вона належить до класу P, а може й ні, але при моєму житті цього ніхто не дізнається», — зізнався Грочоу.

Ласло Бабай працював над проблемою ізоморфізму графів майже 40 років.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.