# 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?

• Here is a tutorial giving an overview of the results on this particular question: cl.cam.ac.uk/~ad260/talks/wollic-tutorial.pdf – Denis Feb 11 at 11:45
• @Denis Thank you, Denis! This tutorial contains more logic structures for P. Traditionally when we talk about a problem is polynomial time solvable, we think it is "easy". However, the logic structures of P look like so complicated, and there are still a lot of unknown cases and open problems. – Rupei Xu Feb 11 at 12:04
• Yes, it would seem that the set of "easy" problems (i.e. P) is not so well-structured, and is hard to characterize with something like "the easy problems are the ones that can be obtained from basic problems A,B,C, combined in ways X,Y". There are always more easy problems that are of another kind, and require clever polynomial algorithms with new ideas in them. – Denis Feb 11 at 19:06