After some reflection, the answer seems to be a trivial 'yes'. We know there is an upper bound on computational complexity, say $f(n)$. If we imagine such an algorithm and each step in the process as a 'yes-no' type procedure, then we simply encode this in an $(f(n) \times f(n))$ diagonal matrix with binary entries on the diagonal. I'm finding it hard to think why this would fail but it should be easy to imagine fixing it.

Ah, wonderful! That is a nice observation and it does not totally surprise me. For my part I'm initially banking on the distance matrix representation, which is obviously a higher complexity than adjacency and Laplacian. Do you know of any results on the complexity of computing distance matrices?

Hi Mikhail - thanks for your comment. What is a 'GI test'?

Hi coudy, thanks for your answer - I'm intrigued by the potential link to harmonic analysis (+1)! However, I'm skeptical about how exhibiting two isometrically distinct tori would appeal to applied mathematicians unless I could show they are isospectral. Could you perhaps spell this out a little more or provide a link to the basic theory which could help me figure this out? It would appear to me (www-fourier.ujf-grenoble.fr/~pberard/D/isos-dea93.pdf) that the tori are isospectral only if the squared lengths of the vertices on the dual lattices are the same, but I may have misunderstood

Hi Joseph, this is a really nice geometric application! However, as you say yourself, I am looking for something a little more in the area of (ostensibly) non-geometric topics such as the likes of PDE theory or analysis, of interest to a broad class of applied mathematicians. As such I might leave the question open for a little bit to see what other people may think about this.