Is graph isomorphism (the decision problem) in $\mathsf{UP}\cap \mathsf{coUP}$? Here $\mathsf{UP}$ is the class of decision problems accepted by an unambiguous Turing machine (see the complexity zoo).
$\begingroup$
$\endgroup$
5
asked Aug 10, 2013 at 12:58
-
5$\begingroup$ Graph isomorphism is in UP. However, $coUP \subseteq coNP$, and we don't whether graph isomorphism is in $coNP$, so the answer is: we don't know. $\endgroup$– Peter ShorAug 10, 2013 at 13:17
-
4$\begingroup$ Can I get a reference for graph isomorphism in UP? $\endgroup$– sdcvvcAug 10, 2013 at 13:50
-
6$\begingroup$ @PeterShor: I was under the impression that GI was not known to be in UP... The set of isomorphisms between two graphs has cardinality either 0 or equal to the size of the automorphism group of one of the graphs, so the "natural" NP algorithm is certainly not a UP algorithm. Did you have some other nondeterministic algorithm for GI in mind that is a UP algorithm? $\endgroup$– Joshua GrochowAug 10, 2013 at 18:18
-
4$\begingroup$ @Joshua: you're right. GI is not known to be in UP. $\endgroup$– Peter ShorAug 10, 2013 at 18:21
-
1$\begingroup$ GI is at least in SZK, the Statistical Zero-Knowledge class; by known containments it's therefore also in AM, coAM, and coNP/poly (coAM is in coNP/poly by standard nonuniform derandomization). This paper, for example, discusses the known upper bounds on SZK: cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf $\endgroup$– Andy DruckerAug 19, 2013 at 20:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
Graph isomorphism is not known to be in $\mathsf{UP}$ nor known to be in $\mathsf{coUP}$.
For $\mathsf{UP}$: the natural nondeterministic algorithm - guess a map between the two graphs and check if it's an isomorphism - has either 0 witnesses (iff the graphs are not isomorphic) or $|\text{Aut}(G)|$ witnesses. Although most graphs have $|\text{Aut}(G)|=1$ (that is, if you pick a random graph on $n$ vertices, the probability that it has any nontrivial automorphsims goes to $0$ quite quickly with $n$), this is not enough to say that there is always at most one witness. This of course does not rule out some other algorithm that could show that graph isomorphism in $\mathsf{UP}$. (After all, it's possible that graph isomorphism is in $\mathsf{P} \subseteq \mathsf{UP}$.)
As for $\mathsf{coUP}$, as pointed out by Peter Shor, we don't even known if graph isomorphism is in $\mathsf{coNP}$, so we certainly don't know if it's in $\mathsf{coUP}$. (Under a plausible derandomization assumption it is in $\mathsf{coNP}$, but I don't know any natural assumption that puts it in either $\mathsf{UP}$ or $\mathsf{coUP}$.)
answered Aug 10, 2013 at 18:44