Języki

Jakie inne problemy występują w językach innych niż izomorfizm grafów w ? Czy możesz podać jakieś referencje?$NP\cap coAM$

Aktualizacja: Zapomniałem wspomnieć, że jestem zainteresowany w językach nie wiadomo, że w .$coNP$

Jedyne inne, o których wiem, to problemy z izomorfizmem: izomorfizm grupowy i izomorfizm pierścieniowy. W protokoły dla obu z nich jest w zasadzie taka sama jak na wykresie izomorfizmie.$coAM$

Grupowy izomorfizm redukuje się do grafu. Izomorfizm redukuje się do izomorfizmu pierścieniowego.

$P$

$O(\sqrt{n/\log(n)})$$NP \cap coAM$$n$$coNP$

$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}$

Złożoność idealnej zerowej wiedzy

Statystyczne języki zerowej wiedzy można rozpoznać w dwóch rundach

$\mathbf{SZK}$