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?

  • 2
    $\begingroup$ 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. $\endgroup$ Commented Jan 29 at 19:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.