10
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Here is a tutorial giving an overview of the results on this particular question: cl.cam.ac.uk/~ad260/talks/wollic-tutorial.pdf $\endgroup$
    – Denis
    Feb 11, 2019 at 11:45
  • $\begingroup$ @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. $\endgroup$
    – user17918
    Feb 11, 2019 at 12:04
  • 1
    $\begingroup$ 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. $\endgroup$
    – Denis
    Feb 11, 2019 at 19:06

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes. There are a lot of algorithmic meta-theorem results(such as the famous Courcelle's theorem) can capture the easy cases, the following link is a good survey paper. people.cs.umass.edu/~immerman/pub/… However, those results also have the restriction for the graph structures on which the problem runs, such as tree, bounded treewidth, planar graphs, minor-closed graphs etc. There are no complete logic structures can capture P in general graphs without order so far. $\endgroup$
    – user17918
    Feb 11, 2019 at 21:57
  • $\begingroup$ I guess that Grohe's work is quite special because in that case the logic exhausts all of P on a remarkably large class of graphs, i.e. there are no counterexamples. If I got it right, being exhaustive is the difficult part. The MSO results you mention do not seem to have this feature. But I my expertise in this regard is very limited, I may be wrong here. $\endgroup$
    – Hermann Gruber
    Feb 12, 2019 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.