# Graph canonization vs. NP

Is graph canonization (GC) in NP? Is it NP-hard? If unknown, what would be your best guess and why?

GC is GI-hard (GI-completeness is unknown), with the graph isomorphism problem being in NP and a candidate for NP-intermediate (unknown if NP-complete/in P).

Babai et al. (1978) mention that finding the lexicographically smallest isomorphic graph is NP-hard. Does that tell us anything about GC in general? My intuition tells me that this is the easiest way to canonize a graph, which would imply that GC is NP-hard and therefore the surprising result $$NP\subseteq QP$$ since $$GC\in QP$$ according to Babai (2019). So my intuition is likely wrong. Can someone explain to me how so?

##### References
• Babai, László et al. (1978): Canonical Labeling of Graphs. ACM.
• Babai, László (2019): Canonical Form for Graphs in Quasipolynomial Time. Preliminary Report.
• Graph canonization is not a decision problem in the first place, hence it makes no sense to ask if it is in NP. (It is not a function problem in the usual sense either, but rather a class of function problems that all share a certain defining property, and the "complexity" of the problem loosely refers to the mimimal complexity of any problem from this class by an abuse of terminology.) Commented Aug 8 at 16:26
• Your intuition is directly contradicted by Babai (2019): the whole reason he obtains a quasipolynomial-time canonization algorithm is that he is doing something much more sophisticated than "lexicographically first isomorphic graph". Commented Aug 8 at 16:31
• @Emil Ah yes, I am referring to the function problem extension here. In my opinion, this should be default. (: Do you know why the lexicographic approach is harder than Babai's? Commented Aug 8 at 17:29
• The lexicographic definition is a trivial brute force construction, hence it cannot be expected to be efficient. Babai’s construction was designed to beat it. There would be no point in publishing a complicated construction if it were not better than the old one. Commented Aug 8 at 17:37
• I think asking whether GC is in TFNP (or NPMV) is still a type error. The issue is that a canonical form is not something that depends only on the input graph, you have to know how the canonical forms of different graphs relate to one another, and this can't be captured in the definition of TFNP / NPMV. Blass & Gurevich (and later, Fortnow and I) introduced complexity classes of equivalence relations precisely to talk about such issues. In our notation, I think your first question is better phrased as something like: is GI in $\mathsf{CF}(\mathsf{NPSV}_t)$? Commented Aug 8 at 23:48

Indeed, not only does that seem to not be the case for GI, but one can prove a separation for other problems assuming only $$\mathsf{P} \neq \mathsf{NP}$$. Blass and Gurevich (SICOMP, 1984) showed that there is an equivalence relation that has a polynomial-time canonical form, but where it's lex least canonical form is "$$\mathsf{\Delta_2 P}$$-complete" in the sense that it is in $$\mathsf{FP}^{\mathsf{NP}} = \mathsf{F\Delta_2 P}$$ and it is $$\mathsf{\Delta_2 P}$$-hard. (For more on related results, see my paper with Fortnow.) As pointed out for GI by