P and Descriptive Complexity In the Complexity Zoo, it says [1] that, in descriptive complexity, $P$ can be defined by three different kind of formulae, $FO(LFP)$ which is also $FO(n^{O(1)})$, and also as $SO(HORN)$. 

However, there are some exceptions, for example, $Evenness$ can not be expressed by FP(FP has the same expressive power with LFP). $Connectivity$ and
$2-colourability$ are not definable by first-order logic. Some problems cannot even be axiomatized with a finite number of variables such as $Evenness$, $Perfect~Matching$, $Hamiltonicity$. 

Immerman proposed that Fixed Point Logic + Counting(FPC) may be a possible logic for capturing P. 

However, Cai Furer, Immerman showed that there are polynomial-time graph properties that are not expressible in FPC[2]. The problem of solving linear
equations over the two element field is not definable in infinitary logic with counting[3]. You may refer to [4] for more details. 

So, what logic structure can capture P in general? The positive answer is that a class of ordered finite structures is definable in least fixed-point logic if, and only if, it is decidable in P by Immerman[5]and Vardi [6]. How about in the unordered case? Can you show more counterexamples of the statement in the complexity zoo?
Martin Grohe made substantial progress on this question recently. He gives a logic capturing polynomial time on classes of graphs embeddable in a fixed surface: https://dl.acm.org/citation.cfm?doid=2371656.2371662
Edit: the general case seems to be unresolved (but I am by no means an expert on this).