# Are classes of graphs represented by adjacency matrix ordered structures?

We know that FO[LFP] captures PTIME on the class of ordered structures. However, I have difficulties interpreting this result. From what I understand, it means that, given a constant, finite alphabet $$\Sigma$$ and a language $$L \subseteq \Sigma^*$$, a Turing machine $$M$$ recognizing the language $$L$$ and a polynomial $$p$$, such that for every word $$w$$ of length $$n$$, $$M$$ halts on $$w$$ after at most $$p(n)$$ steps, exist if and only if there exists a sentence $$\phi$$ of first-order logic with least fixed-point operator over a signature in which every character of the input word is represented by a variable $$x_i, i=1 \dots n$$, we have a linear ordering $$<$$ on $$\Sigma$$ and a binary relation $$r(i, l), i=1 \dots n, l \in \Sigma$$ telling us that character $$i$$ is a particular letter $$l \in \Sigma$$. First of all - is my interpretation of this theorem correct? Secondly, is every language implemented on a computer (e.g. problems on graphs, with graphs represented by adjacency matrices and ordered lexicographically), by definition ordered? We will always need some representation of the data structures we operate on - what are unordered structures really? And do we really have to care about them implementation-wise?

• The ordering is not on $\Sigma$, but on the index set $\{1,\dots,n\}$. But yes: in any realistic implementation on actual hardware, the order is always available. Commented Jan 29 at 19:12