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

29

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

Шива Кинтали
источник

Ответы:

21

Если находится в , то мы получили бы результат: не является неполным, если только . (В настоящее время известно: не является неполным, если только ).гясоNпгяNпNпзнак равносоNпзнак равнопЧАСгяNпΣ2пзнак равноΠ2пзнак равнопЧАС

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

Интересно, что в этом документе они также показывают , что Graph неизоморфность имеет субэкспоненциальные доказательства размера - то есть, - если . Это, по крайней мере, в направлении условного показа .гясоNSUВЕИксппЧАСзнак равноΣ3пгясоNп

Джошуа Грохов
источник
5
Есть еще один результат дерандомизации для от Gutfreund, Shaltiel и Ta-Shma (Равномерная жесткость и случайность для игр Артура-Мерлина, в Computational Complexity 12 (3-4): 85-130, 2003). Этот результат работает при одинаковых допущениях твердости (с обычным предупреждением). AMсоAM
Алон Розен
5

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

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

звездочка
источник
-1

Интересно отметить, что если 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.

Франческо Крис
источник
1
Это довольно тривиально и справедливо для любой проблемы NP.
Каве