<p>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.</p>

<p>Group isomorphism reduces to graph isomorphism reduces to ring isomorphism.</p>

<p>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 <a href="http://dimacs.rutgers.edu/~kayaln/pdf/ringAuto_journal.pdf" rel="noreferrer">Neeraj Kayal, Nitin Saxena. Complexity of Ring Morphism Problems. Computational Complexity 15(4): 342-390 (2006)</a>.</p>

CC BY-SA 2.5
2010-08-21T04:21:51.240Z
2010-08-21T04:21:51.240Z
Joshua Grochow
<p>Another problem is finding approximate solutions to the <a href="http://en.wikipedia.org/wiki/Lattice_problem">shortest or closest vector problem</a> (SVP, CVP). For instance, it has been proven (by <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.594">Goldreich and Goldwasser, 1998</a>) 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$.</p>

<p>On the other hand, it is also known (see <a href="http://doi.acm.org/10.1145/1089023.1089025">Aharonov and Regev, 2004</a>) that finding $O(\sqrt{n})$-approximate solutions is in $NP \cap coNP$.</p>

CC BY-SA 2.5
2010-08-23T19:38:37.233Z
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 http://cstheory.stackexchange.com/questions/330/natural-problems-in-np-cap-conp-not-in-up-cap-coup/337#337"
Joshua Grochow
CC BY-SA 2.5
2010-08-23T13:59:12.873Z
2010-08-23T13:59:12.873Z
MRA
<p>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:</p>

<p><a href="http://portal.acm.org/citation.cfm?id=28418" rel="noreferrer">The complexity of perfect zero-knowledge</a></p>

<p><a href="http://linkinghub.elsevier.com/retrieve/pii/002200009190006Q" rel="noreferrer">Statistical zero-knowledge languages can be recognized in two rounds</a></p>

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

CC BY-SA 2.5
2010-09-05T12:01:59.733Z
2010-09-05T12:01:59.733Z
Sadeq Dousti
<p>What other <strike>problems</strike> languages different than graph isomorphism are in $NP\cap coAM$? Can you give some references?</p>

<p><strong>Update:</strong> I forgot to mention that I'm interested in languages not known to be in $coNP$.</p>

CC BY-SA 2.5
2010-08-20T23:01:37.493Z
You mean those are not known to be in $\mathrm{coNP}$, right?
ilyaraz
CC BY-SA 2.5
2010-08-20T23:09:05.470Z
yes, I forgot to mention that
Marcos Villagra
CC BY-SA 2.5
2010-08-20T23:37:17.203Z
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.
ilyaraz
<cc.complexity-theory><reference-request><complexity-classes><graph-isomorphism>
$NP\cap coAM$ Languages
Marcos Villagra
# $NP\cap coAM$ Languages

(Asked by: username_0 on 2010-08-20)

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

**Tags:** cc.complexity-theory, reference-request, complexity-classes, graph-isomorphism
> **Comments:**
> **username_1**: You mean those are not known to be in $\mathrm{coNP}$, right?  
> **username_0**: yes, I forgot to mention that  
> **username_1**: 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.  

---

## 3 answers

### Answer by username_2 on 2010-08-21. Score: 11

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)](http://dimacs.rutgers.edu/~kayaln/pdf/ringAuto_journal.pdf).


---

### Answer by username_3 on 2010-08-23. Score: 9

Another problem is finding approximate solutions to the [shortest or closest vector problem](http://en.wikipedia.org/wiki/Lattice_problem) (SVP, CVP). For instance, it has been proven (by [Goldreich and Goldwasser, 1998](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.594)) 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](http://doi.acm.org/10.1145/1089023.1089025)) that finding $O(\sqrt{n})$-approximate solutions is in $NP \cap coNP$.

> **Comments:**
> **username_2**: 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 http://cstheory.stackexchange.com/questions/330/natural-problems-in-np-cap-conp-not-in-up-cap-coup/337#337"  

---

### Answer by username_4 on 2010-09-05. Score: 6

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](http://portal.acm.org/citation.cfm?id=28418)

[Statistical zero-knowledge languages can be recognized in two rounds](http://linkinghub.elsevier.com/retrieve/pii/002200009190006Q)

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


---

