From Polynomial Time Queries to Graph Structure Theory

摘要

In a fundamental article on query languages for relational databases, Chandra and Harel [2] asked in 1982 whether there is a language that expresses precisely those queries which can be answered in polynomial time. Gurevich [10] later rephrased the question in the language of finite model theory, asking whether there is a logic that captures polynomial time. Despite serious efforts in the late 1980s and the 1990s, the question is still wide open. It is considered to be one of the main open problems in database theory and finite model theory. Recently, there has been a renewed interest in the question. New languages have been proposed [1, 4, 5] and old ones reconsidered [3, 12], and a number of partial results stating that certain languages capture polynomial time on large and natural classes of structures have been obtained [6, 8, 9, 11]. My talk will be a survey of the state of the art in the "quest for a logic capturing polynomial time." The focus will be on positive results for restricted classes of structures. This will lead us on an excursion to modern graph structure theory, and in particular to Robertson and Seymour's Graph Minor Theory [13]. Besides the references cited in the abstract, the following list contains a reference to the short survey [7].