Сложность задачи о пересечении смежных классов

При условии, что группа симметрии и две подгруппы и , имеет ли место ?$S_n$$G, H\leq S_n$$\pi\in S_n$$G\pi\cap H=\emptyset$

Насколько я знаю, эта проблема известна как проблема пересечения смежных классов. Мне интересно, в чем сложность? В частности, известна ли эта проблема в coAM?

Более того, если ограничено абелевым, то чем становится сложность?$H$

Умеренно экспоненциальное время и (для противоположной задачи, как указано: пересечение Coset обычно считается ответом «да», если смежные классы пересекаются, в отличие от того, как это указано в OQ.)$\mathsf{coAM}$

Лукс 1999 ( бесплатная авторская копия ) дал алгоритм времени, в то время как Бабай (см. Его кандидатскую диссертацию 1983 года, также « Бабай-Кантор-Лукс FOCS 1983» и предполагаемую версию журнала) дал 2 ˜ O ( $2^{O(n)}$-временной алгоритм, который остается самым известным на сегодняшний день. Такизоморфизм графов сводится к квадратичному размеру смежного класса пересечению, улучшая это2 ~ O (п 1 / 4 - е )будетулучшению состояния техники для изоморфизма графов.$2^{\tilde{O}(\sqrt{n})}$$2^{\tilde{O}(n^{1/4-\epsilon})}$

Рассмотрим дополнение, т. Е. Там, где вас просят проверить, является ли . Как я отметил в этом ответе , испытывая ли г ∈ ⟨ г 1 , ... , г к ⟩ есть в NC ⊆ P [1]. Таким образом, вы можете угадать g , h ∈ S n и проверить за полиномиальное время, являются ли g ∈ G , h ∈ H и g π = h . Это дает $G \pi \cap H \not= \emptyset$$g \in \langle g_1, \ldots, g_k\rangle$$\text{NC} \subseteq \text{P}$$g, h \in S_n$$g \in G$$h \in H$$g \pi = h$$\text{NP}$верхняя граница и, следовательно, ваша проблема в .$\text{coNP}$

Редактировать : Это показано в [2, Thm. 15], что проблема пересечения смежных классов находится в . Как отмечено здесь , с. 7, проблема пересечения смежных классов, следовательно, не является NP-полной, если только иерархия времени полинома не разрушится. Кроме того, следует отметить здесь , стр. 6, что Люкс показал, что проблема в P, когда H разрешима, что включает случай H абелева.$\text{NP} \cap \text{coAM}$$\text{P}$$H$$H$

[1]  Л. Бабай, Э. М. Лукс и А. Сресс. Группы перестановок в NC . Proc. 19-й ежегодный симпозиум ACM по теории вычислений, с. 409-420, 1987.

[2] Л. Бабай, С. Моран. Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности . Журнал компьютерных и системных наук, вып. 36, выпуск 2, с. 254-276, 1988.