сертификат coNP для изоморфизма графов

Легко видеть, что изоморфизм графов (GI) находится в NP. Это большая открытая проблема, находится ли GI в coNP. Существуют ли потенциальные кандидаты в свойства графов, которые можно использовать как сертификаты coNP GI. Какие-нибудь домыслы, которые подразумевают ? Каковы некоторые последствия ?$GI \in coNP$$GI \in coNP$

Если находится в , то мы получили бы результат: не является неполным, если только . (В настоящее время известно: не является неполным, если только ).$GI$$coNP$$GI$$NP$$NP=coNP=PH$$GI$$NP$$\Sigma_2 P = \Pi_2 P = PH$

Поскольку находится в , очевидно, что де-рандомизация ( doi link ) поместит , но я не знаю каких-либо возможных свойств графа для помещения противном случае. Я с нетерпением жду больше ответов, хотя!$GI$$coAM$$coAM$$GI \in coNP$$GI \in coNP$

Интересно, что в этом документе они также показывают , что Graph неизоморфность имеет субэкспоненциальные доказательства размера - то есть, - если . Это, по крайней мере, в направлении условного показа .$GI \in co NSUBEXP$$PH = \Sigma_3 P$$GI \in coNP$

Как насчет диапазона (то есть списка, одной записи на ребро) эффективных сопротивлений? Эффективное сопротивление ребра - это вероятность того, что ребро находится в случайном остовном дереве. Эффективные сопротивления могут быть найдены с использованием алгоритмов Спилмана и Тенга, хотя я не знаю, насколько легко это реально реализовать (если кто-то хотел проводить эксперименты).

Предположим, у нас есть два строго регулярных графа, которые имеют одинаковые собственные значения (и мы знаем, что собственные значения не обязательно различают неизоморфные графы). Тогда, если эффективные сопротивления (то есть списки, опять же) одинаковы, их нельзя использовать для различения графиков. Но почему два ко-спектральных графа имеют одинаковое распределение своих ребер в случайных остовных деревьях? Есть ли известная связь между спектром графа и эффективными сопротивлениями графа? то есть, зная спектр спектра, можем ли мы рассчитать эффективные сопротивления?

Интересно отметить, что если GI отсутствует в coNP, то P ≠ NP.

1) Если GI не входит в coNp, то GI ≠ NGI

2) Если GI ≠ NGI, то GI ≠ P

3) Если GI ≠ P, то P ≠ NP

Как следствие из следующих предложений мы имеем: если GI не входит в coNP, то P ≠ NP. То же самое верно, если NGI отсутствует в NP.