Least fixed point logic is efficiently $\operatorname{P}$-bounded for $\operatorname{P} \Leftrightarrow L_\leq$ is a logic for $\operatorname{P}$

A least-fixed point (LFP) formula is $\leq m$-invariant iff f.a. structrues $\mathcal{A}$ with $|A| \leq m$ and all orderings $<_1,<_2$ on $A$

$$(\mathcal{A},<_1) \models_{LFP} \varphi \Leftrightarrow (\mathcal{A},<_1) \models_{LFP} \varphi.$$

The logic $L_\leq$ is defined such that the modelling-relation is

$$\mathcal{A} \models_{L_\leq} \varphi \Leftrightarrow \varphi \textrm{ is \leq m-invariant and } (\mathcal{A},<)\models_{LFP}\varphi \textrm{ for some} <.$$

A logic $L$ is efficiently $\operatorname{P}$-bounded for $\operatorname{P}$ if

• for each $Q \in \operatorname{P}$ there is a $\varphi \in L$ which axiomatizes $Q$
• for each $\varphi \in L$ there is polynomial $p$ such that the modelling relation $\mathcal{A} \models_L \varphi$ can be decided by an algorithm in $\leq p(\|\mathcal{A}\|)$ steps

A known result is that LFP is an efficiently $\operatorname{P}$-bound logic for $\operatorname{P}$ on the class of ordered structures. A paper states that one can easily deduce from the result that $L_\leq$ is a logic for $\operatorname{P}$. Any ideas how?

-
It seems to me that you are probably misreading the paper (Chen and Flum 2010 or 2011? it is always a good idea to include a link to the paper when asking a question about it). It is not known if there is a logic capturing invariant polynomial time queries, the result is a conditional result. – Kaveh Nov 21 '12 at 16:24
Btw, your post is really difficult to parse, e.g. "$P$-bound for $P$" and "$Q \in P$". Please use fonts similar to those used in the paper to make the post more readable. – Kaveh Nov 21 '12 at 16:28
I'm refering to ChenFlum2010 p. 325 bottom. Doesn't the paper state that LFP is a logic capturing $\operatorname{P}$ for the class of unordered structures? – joachim Nov 21 '12 at 18:53
The linked paper and its revision don't have page 325. This is a major open problem in descriptive complexity as far as I know, their result is conditional. – Kaveh Nov 22 '12 at 5:09
I'm sorry. I had different version of the paper. The reference is on page 5 in the upper half. Immerman, Vardi is used as a source. – joachim Nov 22 '12 at 18:58