  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, Furer, 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.
