Why does IFP< not capture PTIME?
The definition of a logic&nbsp;$\mathcal{L}$ capturing a complexity class&nbsp;$\mathcal{C}$ requires that the problem of evaluating $\mathcal{L}$-formulas is itself in&nbsp;$\mathcal{C}$.  However, evaluating formulas of the logic you suggest is coNP-complete (in fact, even without the fixed points).


Membership. You can determine that $\mathfrak{A}\nvDash^* \varphi$ by guessing a linear order and checking that it makes the formula false.
Completeness. A graph is non-3-colourable if, and only if, every linear order $\leq$ on its vertices satisfies the property that, for every pair $x$, $y$ of vertices, at least one of the the vertex sets $\{z\mid z&lt;x\}$, $\{z\mid x\leq z&lt;y\}$ and $\{z\mid y\leq z\}$ contains an edge.  This property is definable without using the fixed point operator.


You could try to get around this by defining the formulas of the logic to be only the order-invariant $\mathrm{IFP}(\tau+&lt;)$ formulas, i.e., those that are true for some linear order if, and only if, they are true for all. But it's an easy consequence of Trakhtenbrot's theorem that this class of formulas is undecidable.