Tenth Annual IEEE Symposium on

Logic in Computer Science (LICS 1995)

Paper: When do Fixed Point Logics Capture Complexity Classes? (at LICS 1995)

Authors: Anil Seth


We give examples of classes of rigid structures which are of unbounded rigidity but Least fixed point (Partial fixed point) logic can express all Boolean PTIME (PSPACE) queries on these classes. This shows that definability of linear order in FO+LFP although sufficient for the least fixed point to capture Boolean PTIME queries, is not necessary even on the classes of rigid structures. The situation however is very different for nonzero- ary queries. We show a two ary PSPACE query which cannot be expressed in PFP on any class of unbounded rigidity of rigid structures. Our results thus show some fundamental differences between expressing Boolean queries and expressing nonzero-ary queries in fixed point logics. Next, we turn to the study of fixed point logics on arbitrary classes of structures. We completely characterize the recursively enumerable classes of finite structures on which PFP captures all PSPACE queries of arbitrary arities. This is one of the main results of this paper. We also state in some alternative forms several natural necessary and some sufficient conditions for the partial fixed point logic to capture PSPACE on classes of finite structures. The conditions similar to the ones proposed above work for the least fixed point logic also in some special cases but to prove these conditions necessary in general for LFP to capture PTIME seems harder and remains open.


    author = 	 {Anil Seth},
    title = 	 {When do Fixed Point Logics Capture Complexity Classes?},
    booktitle =  {Proceedings of the Tenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1995},
    year =	 1995,
    editor =	 {Dexter Kozen},
    month =	 {June}, 
    pages =      {353-365},
    location =   {San Diego, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}