### On polynomial time computation over unordered structures

by Blass and Gurevich and Shelah. [BGSh:760]

J Symbolic Logic, 2002

This paper is motivated by the question whether there exists a
logic capturing polynomial time computation over unordered
structures. We consider several algorithmic problems near the
border of the known, logically defined complexity classes contained
in polynomial time. We show that fixpoint logic plus counting is
stronger than might be expected, in that it can express the
existence of a complete matching in a bipartite graph. We revisit
the known examples that separate polynomial time from fixpoint plus
counting. We show that the examples in a paper of Cai, F{u}rer,
and Immerman, when suitably padded, are in choiceless polynomial
time yet not in fixpoint plus counting. Without padding, they
remain in polynomial time but appear not to be in choiceless
polynomial time plus counting. Similar results hold for the
multipede examples of Gurevich and Shelah, except that their final
version of multipedes is, in a sense, already suitably padded.
Finally, we describe another plausible candidate, involving
determinants, for the task of separating polynomial time from
choiceless polynomial time plus counting.

Back to the list of publications