This book surveys some of the theory of descriptive complexity, which deals with logical descriptions of complexity classes.
It is divided into six chapters, a bibliography and an index. Chapter 1 surveys the basics of complexity theory. Chapter 2 gives some results on first-order logic and finite model theory and expressing complexity classes in a first-order language. Chapter 3 treats generalized quantifiers (introduced by P. Lindström [Theoria 32 (1966), 186–195; MR0244012 (39 #5329)]), which can be used to create extensions of first-order logic which capture the classes L, NL and P [see N. Immerman, SIAM J. Comput. 16 (1987), no. 4, 760–778; MR0899700 (88j:68051)]. In Chapter 4 Arratia-Quesada introduces second-order logic and fixed-point logics, which capture NP [see R. Fagin, in Complexity of computation (Proc. SIAM-AMS Sympos. Appl. Math., New York, 1973), 43–73, SIAM-AMS Proc., VII, Amer. Math. Soc., Providence, R.I., 1974; MR0371622 (51 #7840)] and PSPACE [see S. Abiteboul, M. Y. Vardi and V. Vianu, J. ACM 44 (1997), no. 1, 30–56; MR1438464 (98a:68061)]. Chapter 5 discusses methods to determine definability (variations of Ehrenfeucht-Fraisse games and zero-one laws). Chapter 6 is entitled “P and the dilemma of order”, which deals with the (still open) problem of finding a logic for P. This book is a good introduction for Spanish readers to the study of descriptive complexity.