Войти
 | Нерешенная проблема в информатике :. Можно ли решить проблему изоморфизма графов за полиномиальное время? (другие нерешенные проблемы в информатике) |
Проблема изоморфизма графов - это вычислительная задача определения того, являются ли два конечных графа изоморфными.
Проблема, как известно, не может быть решена ни за полиномиальное время, ни за NP-полный и, следовательно, может относиться к вычислительному классу сложности NP-intermediate. Известно, что проблема изоморфизма графов находится в низкой иерархии класса NP, что подразумевает, что она не является NP-полной, если иерархия полиномиального времени не рухнет. на второй уровень. В то же время изоморфизм для многих специальных классов графов может быть решен за полиномиальное время, и на практике изоморфизм графов часто может быть решен эффективно.
Эта проблема является частным случаем проблемы изоморфизма подграфов , который спрашивает, содержит ли данный граф G подграф, изоморфный другому данному графу H; эта проблема, как известно, NP-полная. Также известно, что это частный случай неабелевой проблемы скрытой подгруппы над симметричной группой .
В области распознавания изображений он известен как точное сопоставление графов.
Наилучшее теоретическое алгоритм разработан Babai Luks (1983) и основан на более ранней работе Luks (1982) в сочетании с субфакторным алгоритмом В.Н. Земляченко (Земляченко, Корнеенко Тышкевич 1985). Алгоритм имеет время выполнения 2 для графов с n вершинами и основан на классификации конечных простых групп. Без теоремы CFSG немного более слабая оценка 2 была получена сначала для сильно регулярных графов Ласло Бабаи (1980), а затем распространен на общие графы Babai Luks (1983). Улучшение показателя √n - большая открытая проблема; для сильно регулярных графов это было сделано Spielman (1996). Для гиперграфов ограниченного ранга субэкспоненциальная верхняя граница, соответствующая случаю графов, была получена Babai Codenotti (2008).
В ноябре 2015 года Бабай объявил о алгоритм квазиполиномиального времени для всех графиков, то есть один со временем работы 
Существует несколько конкурирующих практических алгоритмов для изоморфизма графов, например, предложенных McKay (1981), Schmidt Druffel (1976) и Ullman (1976). Хотя кажется, что они хорошо работают на случайных графах, основным недостатком этих алгоритмов является их экспоненциальная временная производительность в наихудшем случае.
. Проблема изоморфизма графов в вычислительном отношении эквивалентна проблеме вычисления группа автоморфизмов графа и более слабая, чем проблема изоморфизма группы перестановок и проблема пересечения групп перестановок. Для последних двух задач Babai, Kantor Luks (1983) получили оценки сложности, аналогичные оценкам для изоморфизма графов.
Ряд важных частных случаев проблемы изоморфизма графов имеют эффективные решения за полиномиальное время:
Поскольку проблема изоморфизма графов не известна как NP-полный, не поддающийся обработке, исследовательский Она попыталась разобраться в проблеме, определив новый класс GI, набор задач с полиномиальным сокращением Тьюринга к проблеме изоморфизма графов. Если в действительности проблема изоморфизма графов разрешима за полиномиальное время, GI будет равняться P. С другой стороны, если проблема является NP-полной, GI будет равняться NP, и все проблемы в NP будут решены за квазиполиномиальное время.
Как это обычно бывает для классов сложности в иерархии полиномиального времени, проблема называется GI-hard, если есть редукция по Тьюрингу за полиномиальное время от любой задачи в GI к этой задаче, т. е. решение за полиномиальное время проблемы с GI-сложностью дало бы решение за полиномиальное время проблемы изоморфизма графов (и так что все проблемы в GI ). Проблема 
Проблема изоморфизма графов содержится как в NP, так и в co - AM. GI содержится в low для Parity P, а также содержится в потенциально гораздо меньшем классе SPP . То, что он лежит в четности P, означает, что проблема изоморфизма графов не сложнее, чем определение того, имеет ли полиномиальная недетерминированная машина Тьюринга четное или нечетное количество принимающих путей. GI также содержится в низком значении для ZPP. По сути, это означает, что эффективный алгоритм Лас-Вегаса с доступом к NP оракулу может решить изоморфизм графов настолько легко, что он не получит никакой мощности от того, что ему дана возможность делать это в постоянное время.
Существует ряд классов математических объектов, для которых проблема изоморфизма является GI-полной проблема. Некоторые из них представляют собой графы, наделенные дополнительными свойствами или ограничениями:
Класс графов называется GI-полным, если распознавание изоморфизма для графов из этого подкласса является GI-полным проблема. Следующие классы являются GI-полными:
Многие классы орграфов также являются GI -полный.
Помимо проблем изоморфизма, существуют и другие нетривиальные GI-полные проблемы.
Мануэль Блюм и Сампат Каннан (1995) показали вероятностную проверку программ на изоморфизм графов. Предположим, что P - заявленная процедура с полиномиальным временем, которая проверяет, изоморфны ли два графа, но ей не доверяют. Чтобы проверить, изоморфны ли G и H:
Эта процедура полиномиальное время и дает правильный ответ, если P является правильной программой для изоморфизма графов. Если P не является правильной программой, но правильно отвечает на G и H, средство проверки либо даст правильный ответ, либо обнаружит недопустимое поведение P. Если P не является правильной программой и неправильно отвечает на G и H, программа проверки обнаружит недопустимое поведение P с высокой вероятностью или ответит неправильный с вероятностью 2.
Примечательно, что P используется только как черный ящик.
Графики обычно используются для кодирования структурной информации во многих областях, включая компьютерное зрение и распознавание образов и сопоставление графиков, т. Е. Выявление сходства между графами, является важным инструментом в этих областях. В этих областях проблема изоморфизма графов известна как точное сопоставление графов.
В химинформатике и в математической химии проверка изоморфизма графов используется для выявления химическое соединение в химической базе данных. Кроме того, в органической математической химии проверка изоморфизма графов полезна для создания молекулярных графов и для компьютерного синтеза.
Химический поиск в базе данных является примером графического интеллектуального анализа данных, где часто используется подход канонизации графа. В частности, ряд идентификаторов для химических веществ, таких как SMILES и InChI, разработанных для обеспечения стандартных и удобочитаемых человеком способ кодирования молекулярной информации и облегчения поиска такой информации в базах данных и в Интернете, используйте этап канонизации при их вычислении, который по сути является канонизацией графа, представляющего молекулу.
В автоматизации проектирования электроники изоморфизм графов является основой этапа проектирования схемы компоновки и схемы (LVS), который является проверкой того, соответствуют ли электрические схемы , представленный схемой и схемой, одинаковы.
