One Two Three … Ehrenfeucht: Descriptive Complexity and Games

Neil Immerman (Invited Speaker)

9:30 - 10:30AM, Sat, Jun 24.

Descriptive Complexity studies computational complexity via logical descriptions of decision problems. The computational complexity of a decision problem is captured via the richness of the logical language needed to express it. The fundamental tradeoff between number of gates, i.e., amount of computer hardware, and parallel time is exactly captured by the descriptive tradeoff between number of variables and number of quantifiers in first-order logic. Key tools in understanding this descriptive tradeoff are combinatorial games generalizing the Ehrenfeucht-Fraïssé game. We describe these connections, explaining what we know now, recent progress and next steps.

[Back to Schedule]