Доказательство того, что проблема изоморфизма графов не является

10

Проблема изоморфизма графов - одна из самых давних проблем, которая не поддается классификации на или N P -полные задачи. У нас есть доказательства того, что оно не может быть N P -полным. Во-первых, изоморфизм графов не может быть N P -полным, если полиномиальная иерархия [1] не рухнет на второй уровень. Кроме того, подсчитывающая [2] версия GI является тьюрингом полиномиального времени, эквивалентным его версии решения, которая не справедлива ни для одной известной N P -полной проблемы. Счетная версия N P -полных задач, кажется, имеет гораздо более высокую сложность. Наконец, результат малости [3] для GI относительно P P (PNPNPNPNPNPPP ) неизвестно для какой-либо N P -полной задачи. Результат lowness GI был улучшен до S P P G I = S P P после того, как Арвинд и Курур доказали, что GI находится в S P P [4].PPGI=PPNPSPPGI=SPPSPP

Какие другие (недавние) результаты могут служить дополнительным доказательством того, что GI не может быть -завершенным?NP

Я разместил вопрос на Mathoverflow, не получив ответа.

[1]: Уве Шенинг, «Изоморфизм графов в низкой иерархии», Материалы 4-го ежегодного симпозиума по теоретическим аспектам информатики, 1987, 114–124.

[2]: Р. Матон, «Замечание о проблеме подсчета изоморфизмов графов», Письма обработки информации, 8 (1979), стр. 131–132.

[3]: Коблер, Йоханнес; Шенинг, Уве; Torán, Jacobo (1992), "Изоморфизм графов мал для PP", вычислительная сложность 2 (4): 301–330

[4]: В. Арвинд и П. Курур. Изоморфизм графов приведен в SPP, ECCC TR02-037, 2002.

Мухаммед Аль-Туркистани
источник
8
Сколько еще доказательств вам нужно? Позвольте мне перевернуть вопрос: какие есть доказательства того, что GI отсутствует в P?
Лэнс Фортноу
P
2
Косвенным доказательством того, что GI находится в P, является то, что (afaik / afact) никто не может создать не-жесткие экземпляры (даже случайные?), и даже кажется, что нет никаких (предполагаемых) кандидатов. ps этот вопрос кажется близким к тому, какова текущая известная твердость GI
vzn
1
P=NPPΣNP
3
@Arul Смотрите мой комментарий к VZN. В основном, если P = NP, то GI должен быть NP-полным при уменьшении Карпа.
Мухаммед Аль-Туркистани

Ответы:

11

GIQPGINPNPQP=DTIME(npolylogn)EXP=NEXPEXPNEXPGINP

Андрас Фараго
источник