Easier ways to win logical games
Ronald Fagin · DIMACS series in discrete mathematics and theoretical computer science · 1997
The key tool in proving inexpressibility results in finite-model theory is EhrenfeuchtFra iss'e games. This paper surveys various game-theoretic techniques and tools that lead to simpler proofs of inexpressibility results. The focus is on first-order logic and monadic NP. To appear: Proceedings of the DIMACS Workshop on Finite Models and Descriptive Complexity, American Mathematical Society, 1996. 1 Introduction The computational complexity of a problem is the amount of resources, such as time or space, required by a machine that solves the problem. Complexity theory traditionally has focused on the computational complexity of problems. A more recent branch of complexity theory focuses on the descriptive complexity of problems, which is the complexity of describing problems in some logical formalism [Imm89]. One of the exciting developments in complexity theory is the discovery of a very intimate connection between computational and descriptive complexity. In particular, the author ...