On Polynomial Time Computation Over Unordered Structures

Andreas Blass, Yuri Gurevich, Saharon Shelah

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…