Здравствуйте, я в университете столкнулся с задачей, которая связана с изоморфизмом графов, а я не уверен, что знаю об этом достаточно. Может ли кто-нибудь посоветовать хорошую литературу на эту тему?
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:35:12
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
31:35:12
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 09:59:49 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
Я помню что Серёжа Копелёвич (Burunduk1) в 2013 году на зимней школе в Харькове что-то про это рассказывал. Так что, что-то можно найти здесь https://www.youtube.com/playlist?list=PLw3IpZciaVqYv8vCzcuJLpQ8u0i-yAOzu
UPD. Тут только про изоморфизм деревьев
http://logic.pdmi.ras.ru/csclub/sites/default/files/graph_isomorphism_ponomarenko_lecture_notes.pdf
Я например знаю, что статус задачи изоморфизма графов до сих пор открыт (факт из курса теории сложности вычислений), то есть непонятно задача принадлежит P, NP, или же даже образовывает новый класс.
Ну, сегодня(часов так 6 назад) я уже узнал это :). А еще узнал про весьма интересную проблему реконструкции.
Гипотеза Келли-Улама которая?
Да. Она самая.
Уже доказано, что задача не является NP-полной. Читал об этом в заметке Варновского.
"Любопытно, что вопрос о вычислительной сложности задач факторизации, дискретного логарифмирования и распознавания изоморфизма графов интересен прежде всего с точки зрения криптографических приложений, и именно математическая криптография дала инструмент, позволивший, частично и условно, решить проблему их
-полноты. Из теоремы Фортнау [16] и некоторых других результатов следует, что если для какого-либо 
-полного языка существует протокол интерактивного доказательства со статистически нулевым разглашением, то полиномиальная иерархия вырождается. Таким образом, наличие для языка доказательства со статистически нулевым разглашением является косвенным аргументом против его (языка) 
-полноты. Такие доказательства были построены для языков ИЗОМОРФИЗМ ГРАФОВ и КВАДРАТИЧНЫЕ ВЫЧЕТЫ. Следовательно, задача распознавания изоморфизма графов не может быть 
-полной."
http://satisfiability.narod.ru/files/www.cryptography.ru-1169817.html
Кстати, очень интересная статья.
Если я правильно помню, про схлопывание полиномиальной иерархии сейчас тоже ничего не известно. Поэтому утверждение следует читать так: если полиномиальная иерархия не схлопывается, то
. Разве нет?
В конце прошлого года было опубликовано доказательство, что задача изоморфизма графов может быть решена за квази-полиномиальное время. Это также дает основания предполагать, что существует и полиномиальный алгоритм.
https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/ https://habrahabr.ru/post/273231/
Так себе основания, если честно. Аргументы против принадлежности P, да даже NP-complete много фундаментальнее :)
Если честно, я не спец по квази-полиномиальным алгоритмам, я просто перефразировал то, что прочитал в статье:
Года 3 назад в Петрозаводске была задача на проверку графа на изоморфизм snark-графу. Snark-графов было штук 6-7 и нужно было написать перебор с эвристиками.
На науку это конечно не претендует, но достаточно прикольно и интересно.
Авторское решение -- перебор с доказанной асимптотикой.
ОБОЖЕМОЙ, кто-то вспомнил задачу с моего контеста! На самом деле эта задача подразумевалась, как шуточная задача-бонус. Но бонус она принесла только мне в виде геморроя с тестами против хешей.