A Quick Update on the Open Problems in Blass-Gurevich-Shelah’s article “On Polynomial Time Computations Over Unordered Structures”

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]