The small stones. (Les petits cailloux. Une approche modèle-théorique de l’algorithmie.) (English) Zbl 0832.68044

Poizat, Bruno

Lyon: Aléas. 219 p. (1995).

This well written monograph is aimed at graduates of mathematics and information theory. It is devoted to the study of algorithms in models via the use of series of circuits. The monograph is a very good introduction to the theory of algorithms and their complexity from the point of view of circuits, especially for computer scientists who are fluent in French. We give here a brief summary of some of the material covered in the book. In the preface the author discusses the algorithmic heritage of the Romans (who calculated with little stones – whence, the title of the book), the Gauls, the Franks, the Arabs, the Indians and the Chinese. The author considers structures \(M\) with a finite family of operations and relations and algorithms that enable computation in \(M\). An algorithm should be appreciated by how efficient is it. The principal measure of such efficiency is the time necessary to complete the computation. This is evaluated as a function of the length \(n\) of the given input. A desirable property of an algorithm is that the time required for computation be bounded by \(p(n)\), where \(p(n)\) is a polynomial.
The author illustrates the concept of algorithm in Chapter 1 by the four arithmetic operations, systems of linear equations, linear Boolean equations, polynomial Boolean equations and linear equations with integer coefficients. A set \(X \subseteq M_*\) is said to have property \(P\) if its characteristic function can be computed by an algorithm running in polynomial time. The set \(X\) has property \(NP\) if there is a set \(Y \subseteq M_*\) with property \(P\) and a polynomial \(q(n)\) such that \(x \in X\) iff there is \(y\in M_*\) of length at most \(q(n)\) where \(n\) is the length of \(x\) such that \(xy\in Y\). The author discusses whether the property \(P\) is equivalent to the property \(NP\) for specific structures. In Chapter 2, the author defines a Boolean circuit as a finite directed graph without directed cycles in which every vertex has at most two arrows ending and at most one arrow begins. The inputs are the sources of the graph and the outputs are the sinks of the graph. The vertices ending exactly 2 arrows are labeled by either a join or a meet, the inputs are labeled by variables or the constants 0, 1 and the vertices ending exactly one arrow are labeled by either negation or the identity function.
A circuit for a structure \(M\) is similar to a Boolean circuit except for each \(n\)-ary operation a vertex ending \(n\) arrows is allowed. The author shows how to replace an algorithm by a sequence of circuits \(C_n\) where the \(n\)-th circuit determines the computation for inputs of length \(n\). Chapter 3 is devoted to structures and replacing relations by functions; i.e., model theory in the spirit of circuitry. In Chapter 4, the author briefly introduces computability in structures of finite types. The property \(P\) is generalized to the property \(\mathbf P\). The principal difference is that for \(P\) the function assigning the circuit \(C_n\) to the value \(n\) is required to be computable by a uniform algorithm running in polynomial time, while for \(\mathbf P\) no demand is made on this function except for the fact that the growth of the circuit length be polynomial in \(n\). In Chapter 5, the author studies Boolean computations in special structures such as locally finite structures and Koiran theorems concerning the real numbers with diverse operations. The general setup for a structure \(M\) is discussed and some Boolean problems with property \(P\) or \(\mathbf P\) are compared for various structures. In Chapter 6, the author describes polynomial existential quantifiers enabling the definition of the classes with properties \(NP\) and \({\mathbf N} P\) as members of a “logical hierarchy”. He discusses the problem of whether \(P = NP\) or \({\mathbf P} = {\mathbf N} P\) and shows that whether \(P = NP\) corresponds to an algorithmic version of quantifier elimination. In Chapter 7, the author elaborates on the study begun in Chapter 5 and states that the existence of structures for which \(P = NP\) remains open. The final Chapter 8 is devoted to the polynomial hierarchy in which \(P\) and \(NP\) are the first members and is modeled after the hierarchy of first order formulae of type \(\exists\), \(\forall\), \(\exists \forall\), \(\forall \exists\), \(\exists \forall \exists\), …. Each chapter concludes with a number of exercises and biographical notes relevant to the material expounded.

Reviewer: A.A.Iskander (Lafayette)

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15	Complexity of computation (including implicit computational complexity)
94C10	Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
03C10	Quantifier elimination, model completeness, and related topics
68-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

Keywords:

algorithm; Boolean equations; Boolean circuit; quantifier elimination