A Logic for P: Are we Nearly There Yet?

Whether or not there is a logic for P is the classic problem of descriptive complexity theory. It has been an open problem for over four decades (since its first formulation by Chandra and Harel 1980) now and much has been written about it, including surveys and textbook presentations (see, for instance Ebbinghaus and Flum 1999, Chapter 11. The problem remains a focus of active research and there have been significant recent developments related to it. These may not be well known outside a specialist group of researchers and one aim of the present article is to bring these to a wider audience. To place the new results in their context, we begin with a wider perspective on the question.