Barthélémy, J.-P. (F-ENST2);
Cohen, G. [Cohen, Gérard Denis] (F-ENST);
Lobstein, A. (F-CNRS)
* Complexité algorithmique et problèmes de communications.
(French) [Algorithmic complexity and communication problems]
With a preface by M. Minoux.
Collection Technique et Scientifique des Télécommunications.
[Scientific and Technical Collection on Telecommunications]
Masson, Paris, 1992. xxviii+228 pp. 170 F. ISBN 2-225-82672-2
The book represents a clear, synthetical and deep presentation of the problem P =? NP. It contains six chapters (Problems and languages, Classes P and NP, NP-hard problems, Complexity and coding, Complexity and cryptology, Vector optimization). It is a serious, updated rival of the famous Garey-Johnson 1979 book. As in most cases in the history of mathematics, the challenging open problem P =? NP generates many other problems, often interesting in themselves.
Cristian Calude (NZ-AUCK-C)