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$
$\endgroup$
3
-
$\begingroup$ You mean those are not known to be in $\mathrm{coNP}$, right? $\endgroup$– ilyarazCommented Aug 20, 2010 at 23:01
-
$\begingroup$ yes, I forgot to mention that $\endgroup$– Marcos VillagraCommented Aug 20, 2010 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$– ilyarazCommented Aug 20, 2010 at 23:37
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
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).
answered Aug 21, 2010 at 4:21
$\begingroup$
$\endgroup$
1
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$ Commented Aug 23, 2010 at 19:38
$\begingroup$
$\endgroup$
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).
answered Sep 5, 2010 at 12:01