Is there a logic for polynomial time?
H-D Ebbinghaus · Logic Journal of IGPL · 1999
The paper gives an introduction to the problem whether there is a logic ℒ that captures PTIME in the sense that, via some natural encoding, the classes of finite structures axiomatizable in ℒ correspond to the languages in PTIME. It discusses several notions of capturing, thereby giving a picture of the general theory. The question for the most important version is still open. The paper surveys positive answers for certain classes of graphs that are based on the method of canonization. Keywords:finite model theory, descriptive complexity, Ptime, canonization