A Quick Update on the Open Problems in Blass-Gurevich-Shelah's article \On Polynomial Time Computations Over Unordered Structures"
Andreas R. Blass, Yuri G. Gurevich · 2005
The Blass-Gurevich-Shelah article in the title is [On Polynomial Time Computation Over Unordered Structures]. The open problems are formulated in Section 7. They all are yes/no questions. There are two lists of open questions. The first list contains four open questions. And then there is a list of two additional open questions. Here we recall the six questions, review their current status, and use this opportunity to advertise a related open question by Benjamin Rossman. This update is of December 2005. We presume that the reader is familiar with the article [On Polynomial Time Computation Over Unordered Structures]