I have a (hopefully simple, maybe dumb) question on Babai's landmark paper showing that $\mathsf{GI}$ is quasipolynomial.
Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for $i\in\{1,2\}$ are isomorphic, in time quasipolynomial in $v=|V_i|$.
Did Babai actually show how to find an element $\pi\in S_v$ that permutes the vertices of $G_1$ to $G_2$, or is the certificate merely an existence-statement?
If an oracle tells me that $G_1$ and $G_2$ are isomorphic, do I still need to look through all $v!$ permutations of the vertices?
I ask because I also think about knot equivalence. As far as I know, it's not known to be, but say detecting the unknot were in $\mathsf{P}$. Actually finding a sequence of Reidemeister moves that untie the knot might still take exponential time...