Sprachen

Welche anderen Problemsprachen als der Graphisomorphismus gibt es in ? Können Sie einige Referenzen nennen?$NP\cap coAM$

Update: Ich habe vergessen zu erwähnen, dass ich an Sprachen interessiert bin, von denen nicht bekannt ist, dass sie in .$coNP$

Die einzigen anderen, die ich kenne, sind auch Isomorphismusprobleme: Gruppenisomorphismus und Ringisomorphismus. Die -Protokolle für beide sind im Wesentlichen dieselben wie für den Graphisomorphismus.$coAM$

Gruppenisomorphismus reduziert sich auf Graphisomorphismus reduziert sich auf Ringisomorphismus.

$P$

$O(\sqrt{n/\log(n)})$$NP \cap coAM$, where $n$ denotes the dimension of the lattice. It is not known whether this problem is in $coNP$.

On the other hand, it is also known (see Aharonov and Regev, 2004) that finding $O(\sqrt{n})$-approximate solutions is in $NP \cap coNP$.

Well, I know that $\mathbf{NP}\subseteq\mathbf{AM}$, and every language possessing statistical zero-knowledge proofs fall in $\mathbf{AM}\cap\mathbf{coAM}$. Symbolically, $\mathbf{PZK}\subseteq \mathbf{SZK}\subseteq \mathbf{AM}\cap\mathbf{coAM}$. (Where $\mathbf{PZK}$ is the class of languages admitting perfect zero knowledge, and $\mathbf{SZK}$ is the class of languages admitting statistical zero knowledge). See the following links for the proof:

The complexity of perfect zero-knowledge

Statistical zero-knowledge languages can be recognized in two rounds

Languages like shortest or closest vector problem (SVP, CVP) fall in $\mathbf{SZK}$ (see the paper by Goldreich and Goldwasser, cited above).