Immerman and Vardi showed in the early 1980s that the logic LFP, augmented with an ordering, can express all PTIME-decidable properties. In 1997, Makowsky conjectured that LFP+A, i.e. LFP augmented with an arbitrary relation A, captures PTIME if and only if a total ordering is parametrically definable on A using LFP. This would establish that LFP's computational power crucially depends on the input being ordered.

In this paper, we disprove Makowsky's conjecture by giving a class of relations A such that LFP+A captures PTIME, yet no ordering with more than O(n^1/2) elements can be defined on A.