What other problems languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references?

Update: I forgot to mention that I'm interested in languages not known to be in $coNP$.

  • $\begingroup$ You mean those are not known to be in $\mathrm{coNP}$, right? $\endgroup$
    – ilyaraz
    Aug 20 '10 at 23:01
  • $\begingroup$ yes, I forgot to mention that $\endgroup$ Aug 20 '10 at 23:09
  • $\begingroup$ But it is believed that $\mathrm{coNP} = \mathrm{coAM}$, so the best way to formulate the question is to replace believed by known. Sorry for my pedantism. $\endgroup$
    – ilyaraz
    Aug 20 '10 at 23:37

The only other ones I know of are also isomorphism problems: group isomorphism and ring isomorphism. The $coAM$ protocols for both of these are essentially the same as for graph isomorphism.

Group isomorphism reduces to graph isomorphism reduces to ring isomorphism.

Interestingly, unlike (what is known for) groups and graphs, for rings, determining whether a ring has a nontrivial automorphism is in $P$, while finding a nontrivial automorphism is equivalent to factoring integers. See Neeraj Kayal, Nitin Saxena. Complexity of Ring Morphism Problems. Computational Complexity 15(4): 342-390 (2006).


Another problem is finding approximate solutions to the shortest or closest vector problem (SVP, CVP). For instance, it has been proven (by Goldreich and Goldwasser, 1998) that approximating SVP within a factor of $O(\sqrt{n/\log(n)})$ is in $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$.

  • 2
    $\begingroup$ These are search problems, not decision problems, and the decision variants of the approximation problems are promise problems. Andy Drucker and I had a similar discussion about SVP and CVP at cstheory.stackexchange.com/questions/330/…" $\endgroup$ Aug 23 '10 at 19:38

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.