Языки

Какие еще языки проблем, отличные от изоморфизма графов, есть в ? Можете ли вы дать некоторые ссылки?$NP\cap coAM$

Обновление: Я забыл упомянуть , что я заинтересован в языках , не известно, в .$coNP$

Единственные другие, о которых я знаю, это также проблемы изоморфизма: групповой изоморфизм и кольцевой изоморфизм. Протоколы для них обоих по существу такие же, как и для изоморфизма графов.$coAM$

Групповой изоморфизм сводится к графу изоморфизм сводится к кольцевому изоморфизму.

Интересно, что в отличие от (что известно для) групп и графов для колец, определение того, имеет ли кольцо нетривиальный автоморфизм, находится в , а нахождение нетривиального автоморфизма эквивалентно факторизации целых чисел. См. Нирадж Каял, Нитин Саксена. Сложность проблем кольцевого морфизма. Вычислительная сложность 15 (4): 342-390 (2006) .$P$

Другая проблема заключается в поиске приближенных решений самой короткой или ближайшей векторной задачи (SVP, CVP). Например, было доказано ( Goldreich and Goldwasser, 1998 ), что аппроксимация SVP с коэффициентом находится вNP∩coAM, гдеnобозначает размерность решетки. Не известноли эта проблема всONP.$O(\sqrt{n/\log(n)})$$NP \cap coAM$$n$$coNP$

С другой стороны, также известно (см. Ааронов и Регев, 2004 ), что нахождение -approximate растворы вNPПсõNP.$O(\sqrt{n})$$NP \cap coNP$

$\mathbf{NP}\subseteq\mathbf{AM}$$\mathbf{AM}\cap\mathbf{coAM}$$\mathbf{PZK}\subseteq \mathbf{SZK}\subseteq \mathbf{AM}\cap\mathbf{coAM}$$\mathbf{PZK}$$\mathbf{SZK}$

Сложность совершенного нулевого знания

Статистические языки с нулевым знанием могут быть признаны в два раунда

$\mathbf{SZK}$