tag:blogger.com,1999:blog-12932458.post112959279489050123..comments2023-09-29T09:03:36.236-05:00Comments on Logicomp: Logics capturing complexity classesanthonywlinhttp://www.blogger.com/profile/07618509800342861247noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-12932458.post-1129689089486602842005-10-18T21:31:00.000-05:002005-10-18T21:31:00.000-05:00Kenny: you can indeed think of the least fixed poi...Kenny: you can indeed think of the least fixed point operator as some sort of "built-in" partial order with limited capability (i.e. you can only pick "the least fixed point").<BR/><BR/>On a related note, there is a fixed point operator that gives you a "minimal fixed point" (not necessarily least). Finite model theorists (and I guess, also database theorists) call this operator "inflationary fixed point operator". Both FO+LFP and FO+IFP capture PTIME over ordered structures.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1129688288004849222005-10-18T21:18:00.000-05:002005-10-18T21:18:00.000-05:00David Molnar: 1. Answer to your first question: no...David Molnar: <BR/>1. Answer to your first question: not that I know of. [I assume you ask this question for the hope that we can get increasingly "stronger" results so that a logic for PTIME will be finally obtained. See item 3 for another direction people have tried.] <BR/>2. Answer to your second question: I can give you one possible (although trivial) relaxation of a linear order: the "immediate successor" relation. I think FO+LFP still captures PTIME over all finite structures with external successor relations. This is because you can define a linear order using an external successor relation + fixed point operator. [Notice that without fixed point operator, FO cannot define a linear ordering even though you are given an external successor relation.]<BR/>3. On the other hand, some people have tried to find a logic that captures PTIME over "restricted classes of finite structures with no external linear orders". Martin Grohe has a beautiful result that says that the logic FO+LFP+(some counting quantifier) captures PTIME over the class of all finite structures, both ordered and unordered, of bounded treewidth. To the best of my knowledge, this is the strongest possible result we have gotten in this particular direction.<BR/>4. At the end of the day, one has to ask what we mean by a "logic". It seems that there are quite a few, not necessarily equivalent, definitions of the term logic. Alan Nash, Jeff Remmel, and Victor Vianu have recently published a nice paper on this issue. As far as I remember, their thesis is that each definition may lead to a different answer to whether there is a logic for PTIME.anthonywlinhttps://www.blogger.com/profile/07618509800342861247noreply@blogger.comtag:blogger.com,1999:blog-12932458.post-1129607948088612592005-10-17T22:59:00.000-05:002005-10-17T22:59:00.000-05:00Is there some natural relaxation of a linear order...Is there some natural relaxation of a linear ordering that is considered by logicians? Naively, I might try to define an ordering for which "not too many" elements are incomparable. If there exist such relaxations, do there exist any such that we know a logic for P with such a relaxed ordering?Anonymousnoreply@blogger.com