10
$\begingroup$

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

$\endgroup$
  • 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 Shor Aug 10 '13 at 13:17
  • 4
    $\begingroup$ Can I get a reference for graph isomorphism in UP? $\endgroup$ – sdcvvc Aug 10 '13 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 Grochow Aug 10 '13 at 18:18
  • 4
    $\begingroup$ @Joshua: you're right. GI is not known to be in UP. $\endgroup$ – Peter Shor Aug 10 '13 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 Drucker Aug 19 '13 at 20:04
19
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.