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ü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 possible candidate, involving determinants, for the
task of separating polynomial time from choiceless polynomial time plus counting.