How is the knot equivalence problem represented?
By this I mean I am looking for an analogy that compares with graph equivalence. For graph equivalence, we have two graphs $G_1$ and $G_2$ with adjacency matrices $A$ and $B$ respectively and we seek if there is a permutation matrix $P$ with transpose $P'$ such that $A=PBP'$.
Is there an analogous matrix theoretic framework for knot equivalence? For any decision problem input have to be polynomially sized.
By knot, I assume you mean a knot in $S^3$. Typically a knot is encoded as a diagram, which you might think of as a tetravalent planar graph, with some kind of description of undercrossings and overcrossings, say by some kind of labelling of the half edges incident to every vertex. Abstractly, the notion of equivalence is ambient isotopy; combinatorially, in terms of the diagram, there are the three types of Reidemeister moves.
There are other data types used (like self-avoiding cycles in the integer lattice, or triangulations of $S^3$ together with a cycle in its 1-skeleton), but they will all differ essentially from (finite) graphs in the following way: for any given knot type, there will be infinitely many descriptions of it in that data type. So equivalence will not be as "simple" as conjugation by a permutation matrix. Instead, a priori, one must search through an infinite collection of descriptions related by local moves. Improving on this, Lackenby has shown a polynomial bound on the number of Reidemeister moves to recognize an unknot. More generally, given the current state of things, it's entirely possible knot equivalence is in $\mathsf{P}$.
