<p>Graph isomorphism is not known to be in $\mathsf{UP}$ nor known to be in $\mathsf{coUP}$. </p>

<p>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}$.)</p>

<p>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}$.)</p>

CC BY-SA 3.0
2013-08-10T18:44:56.203Z
2013-08-10T18:44:56.203Z
Joshua Grochow
<p>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 <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up" rel="nofollow">complexity zoo</a>). </p>

CC BY-SA 3.0
2013-08-10T13:17:33.937Z
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.
Peter Shor 
CC BY-SA 3.0
2013-08-10T13:50:58.417Z
Can I get a reference for graph isomorphism in UP?
sdcvvc
CC BY-SA 3.0
2013-08-10T18:18:45.637Z
@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?
Joshua Grochow
CC BY-SA 3.0
2013-08-10T18:21:39.473Z
@Joshua: you're right. GI is not known to be in UP.
Peter Shor 
CC BY-SA 3.0
2013-08-19T20:04:52.907Z
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:    http://www.cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf
Andy Drucker
<cc.complexity-theory><graph-isomorphism>
Is graph isomorphism in UP ${\cap}$ coUP?
Fayez Abdlrazaq Deab
# Is graph isomorphism in UP ${\cap}$ coUP?

(Asked by: username_0 on 2013-08-10)

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](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:U#up)).

**Tags:** cc.complexity-theory, graph-isomorphism

> **Comments:**
> **username_1**: 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.  
> **username_2**: Can I get a reference for graph isomorphism in UP?  
> **username_3**: @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?  
> **username_1**: @Joshua: you're right. GI is not known to be in UP.  
> **username_4**: 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:    http://www.cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf  

---

## 1 answers

### Answer by username_3 on 2013-08-10. Score: 20 | Accepted answer

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


---

