Computational complexity. Theory, techniques, and applications. In 6 volumes.

*(English)*Zbl 1278.68001
Springer Reference. Berlin: Springer (ISBN 978-1-4614-1799-6/hbk; 978-1-4614-1800-9/ebook; 978-1-4614-1801-6/hbk+ebook). xliv, 3492 p. (2011).

This book, edited by Robert A. Meyers, is concerned with complex systems. It provides a broad and at times also in-depth overview of different aspects of the field of complex systems and embraces the term in its broad sense. It has an emphasis on formal aspects, in particular computational complexity. It has encyclopedic aspirations but actually is a collection of articles by a large number of different authors on different topics.

The compendium was published in 2012 and consists of selections from the Encyclopedia of complexity and system sciences from 2009 [R. A. Meyers, (ed.), Encyclopedia of Complexity and System Sciences. 11 Volumes. New York, NY: Springer (2009; Zbl 1171.93001)]. It covers a modern, lively aspect of science and, therefore, at places the age shows, in particular in but not restricted to the references.

The work is more than 3500 pages long and comes in six volumes. The table of contents contains page numbers and remains silent about volume numbers, making navigation unnecessary tedious. The articles are sorted alphabetically with respect to their titles so that if a title is known it can be found without the help of the table of contents equally fast.

There are 209 articles and since they are sorted alphabetically with respect to the titles they range from ‘Additive cellular automata’ by Burton Voorhees to ‘Zero-sum two person games’ by T. E. S. Raghavan. Some of the subjects are covered in great detail, e. g., there are 29 articles about cellular automata, 11 articles about quantum computing, 10 articles about social networks, and 8 articles about granular computing in a narrow sense. The 209 articles are organized in 14 sections, 13 of which come with an introduction. They have varying numbers of articles (and, consequently, varying levels of detail), and each of the 14 different sections is in the editorial responsibility of one of the 13 section editors. More precisely:

– Agent based modeling and simulation (14 articles), edited by Filippo Castiglione;

– Mathematical basis of cellular automata (29 articles), edited by Andrew Adamatzky;

– Complex networks and graph theory (14 articles), edited by Geoffrey Canright;

– Data mining and knowledge discovery (10 articles), edited by Peter Kokol;

– Game theory (28 articles), edited by Marilda Sotomayor;

– Granular computing (23 articles), edited by Tsau Y. Lin;

– Intelligent systems (6 articles), edited by James A. Hendler;

– Probability and statistics in complex systems (18 articles), edited by Hendrik Jeldtoft Jensen;

– Quantum information science (9 articles), edited by Joseph F. Traub;

– Social network analysis (11 articles), edited by John Scott;

– Physics and mathematics applications in social science (3 articles), edited by Andrzej Nowak;

– Soft computing (12 articles), edited by Janusz Kacprzyk;

– Unconventional computing (21 articles), edited by Andrew Adamatzky;

– Wavelets (11 articles), edited by Edward Aboufadel.

These 13 section editors peer-reviewed the articles of their sections (with the help of the main editor Robert A. Meyers and the board members Richard E. Stearns, Stephen Wolfram, and Lotfi A. Zadeh) and have selected articles for inclusion. This procedure is supposed to assure ‘that the reader can have a level of confidence in the relevance and accuracy of the information exceeding that generally found on the World Wide Web’ (preface, page VI, contained in each volume). Clearly, this applies to the time of the first publication in 2009.

The 13 section editors are from five different countries, namely the USA (4 editors), the UK (3 editors), Poland (2 editors), and one from each of Brazil, Italy, Norway, and Slovenia. The authors of the 209 articles come from 33 different countries and their geographical distribution reflects to some degree that of the section editors, the most common countries being the USA (100 authors), the UK (25 authors), France (19 authors), Poland (17 authors), Canada (15 authors), Germany (14 authors), Italy (13 authors), Israel (11 authors), Slovenia (10 authors), Spain (10 authors), and all other countries with less than 9 authors (where a single author may be counted for more than one country if he or she listed more than one affiliation).

All articles start with a miniature table of contents (called article outline), a glossary, and a definition of the subject. The glossary contains short definitions of the article’s central terms. The ‘Definition of subject’ explains what the article is about and usually also contains a motivation. Since many central topics are covered in numerous articles one finds the definition of some central terms in many glossaries. Since the glossaries have different authors these definitions differ. This clearly is very different from what one would expect to find in an encyclopedia but it is not necessarily a bad thing. Instead of a single definitive definition one can find numerous attempts at definitions, using different wordings and having different emphasis.

The articles contain concise descriptions, usually with precise statements including formal definitions and theorems. They come with a large number of figures, many of them in color. In general, they do not contain proofs but pointer to relevant literature instead. All articles (with the exception of most section introductions) contain a list of references. Many have in addition to this a list of books and reviews containing a more detailed and in-depth study of the article’s subject.

Homogeneity is restricted to the format of the articles, in the writing one finds all variety in style, degree of formality, and focus that one can expect from an edited volume. This independence of the authors is a strength since it allows central topics to be discussed from quite different perspectives. It is also a weakness since there are no references between the articles (apart from the section introductions). Where an article mentions the central topic of another article it is up to the reader to make this connection and find out where he or she can find more details.

Naturally, the articles reflect who their authors are. For articles with a very broad subject this can be a disadvantage. E. g., the article ‘Stochastic processes’ by Alan J. McKane (from the section ‘Probability and statistics in complex systems’) restricts its attention mostly to Markov chains and is clearly written from the perspective of physics. Even the list of books and reviews that contains [N. Wax et al., Selected papers on noise and stochastic processes. New York: Dover Publications (1954; Zbl 0059.11903)] as its only entry completely ignores the enormous body of mathematical treatments of the subject. On the other hand, when articles have a narrower focus and are written by one of the leading experts in the field, they are very useful, see ‘Immunecomputing’ by Jon Timmis for an excellent example.

The sheer size of the work makes an index highly desirable. There is indeed a lengthy index spanning 75 pages. Since the vast majority of the index terms comes with exactly one page number its usefulness is limited. More useful is the list of glossary terms with page numbers (but again without volume numbers) that on 18 pages contains all terms defined in any of the 197 glossaries.

With the exception of the section on ‘Physics and mathematics applications in social science’ each section comes with a (sometimes brief) overview article authored by the section editor. In most cases these articles can be recognized by having ‘Introduction to <section title>’ as their title. There are, however, exceptions to this rule (in the sections ‘Complex networks and graph theory’ and ‘Social network analysis’). These introductions provide a useful overview and pointers to the different articles of the section. Since the compendium is sorted alphabetically by title and not organized by sections these introductions are a bit hidden. It is worth the effort to look out for them.

The section on ‘Agent based modeling and simulation’ contains articles introducing and discussing this computational modeling paradigm including definitions, mathematical, and logical foundations. Other articles discuss implementation aspects on different levels. The section considers connections to artificial life, cellular automata, physics, computational economics, swarm intelligence, robotics, and games in some detail. Moreover, it contains articles concerned with applications, namely modeling of tumor invasion and for social phenomena simulation.

The section on ‘Mathematical basis of cellular automata’ contains detailed articles about many different foundational aspects of cellular automata, including their definition and categorization. Their is an emphasis on cellular automata in non-standard settings, i. e., different from the orthogonal grid. Several articles are devoted to the study of the dynamic behavior of cellular automata, including one article solely about gliders. Specific variants are discussed in their own articles, considering additive cellular automata, cellular automata with memory, quantum cellular automata, reversible cellular automata, structurally dynamic cellular automata, respectively. The articles dealing with mathematical foundations in a more narrow sense consider universality, group theoretic aspects, connections to algorithmic complexity and language theory, tiling problems, the firing squad synchronization problem, as well as cellular automata as models of parallel computation. There are also articles dealing with more application-oriented aspects like modeling of physical systems and growth phenomena including resulting effects like phase transitions and self-organized criticality.

The section on ‘Complex networks and graph theory’ contains articles laying groundwork by introducing classical concepts and results about random graphs and directed graphs, respectively. Several articles discuss specific examples for complex networks including food networks, gene regulatory networks, human sexual networks, internet topology, and the world wide web. More general or abstract concepts are also considered, e. g., growth models and motifs. In addition, one article is devoted to the subject of visualization of complex networks.

The section on ‘Data mining and knowledge discovery’ covers the role of artificial neural networks, case based reasoning, and rough sets in this area. Decision trees and ensemble methods are discussed. Two articles deal with dimensionality reduction. Attention is also paid to knowledge discovery. One article discusses the role evolutionary algorithms can play and contains a decent introduction to evolutionary algorithm that, however, is very cursory on the theory side and does not even touch the topic of computational complexity.

The section on ‘Game theory’ contains a number of articles that present clear and accessible descriptions of the different types of games, namely cooperative games, zero-sum two player games, stochastic games, inspection games, differential games, static games and dynamic games. There is an emphasis on repeated games with articles covering repeated games with complete information, with incomplete information, and reputation effects. The subject is often treated from the perspective of economics, covering topics like mechanism design, implementation theory, cost sharing, fair division, strategic complexity in game theory, market games and clubs. Applications are also discussed, examples include voting, evolutionary game theory, networks and stability.

The section on ‘Granular computing’ contains introductory articles (including a rather philosophical discussion of the subject) as well as a number of articles that discuss the role granular computing has to play in interaction with data mining, fuzzy logic and control, rough set theory, grid and cloud computing, and social networks. This choice of topics implies overlaps with three other sections, namely the section on ‘Data mining and knowledge discovery’, ‘Social network analysis’, and ‘Soft computing’, where fuzzy logic and rough sets are treated. Since there granular computing is not a topic this overlap actually is an advantage for the treatment of granular computing since an independent view on the same topics is available.

Intelligent systems is a research area that has huge overlaps with the topics of other sections. Consequently, the section on ‘Intelligent systems’ contains in some sense the leftovers, five articles on different aspects of intelligent systems that would not fit anywhere else. These are about learning and planning, mobile agents, and applications of intelligent systems in the areas of control, modeling, simulation, and the semantic web. It comes as a natural consequence of its topic that the section on ‘Probability and statistics in complex systems’ contains articles of a more abstract and fundamental level than most of the other sections. The section covers modeling of complex systems, phenomenology, and analysis of data from complex systems. Some of the articles have some tendency to favor a point of view that stems from physics. On the other hand the section contains overview articles on modern mathematical tools that either have the proven ability or potential to be extremely useful in dealing with complex systems. Examples include random walks, branching processes, correlations, entropy, extreme value statistics, random matrix theory, and stochastic LĂ¶wner evolution.

The section on ‘Quantum information science’ provides an overview of the major areas in quantum computing. It covers quantum algorithms, quantum computational complexity as well as quantum complexity for continuous problems. Moreover, it contains articles about implementation aspects, i. e., quantum computing with trapped ions, quantum computing using optics and quantum error correction, and finally a classic application area, quantum cryptography.

It may be a bit surprising to find a complete section on ‘Social network analysis’ in a computer science book since the research area originated in the social sciences. The articles in this section cover graph theoretical approaches, various modeling and analytical approaches and include one article about the visualization of social networks.

The section on ‘Physics and mathematics applications in social science’ contains only three articles (and no introduction). One article covers a simple adaptive multi-agent model of financial markets, called minority game, that has drawn considerable attention since its introduction in 1997 [D. Challet and Y.-C. Zhang, “Emergence of cooperation and organization in an evolutionary game”, Physica A 246, 407–418 (1997)]. The article describes the original setting and many variants, various analytical approaches and applications. Another article gives a broad overview of different models and theories about rational, goal-oriented agents. The third article provides an overview of different simulation models for social processes.

Soft computing is usually used as an umbrella term that covers the research areas of artificial neural networks, evolutionary computation (and, possibly, even broader nature-inspired computing), and fuzzy logic. The section on ‘Soft computing’ here narrows the term down to fuzzy logic and its applications only. The articles in this section cover the basics of fuzzy logic and fuzzy operators, rough sets and possibility theory, fuzzy optimization, as well as hybrid systems, including neuro-fuzzy systems.

The section on ‘Unconventional computing’ covers a very diverse set of approaches to computing that lack a common theme unless one considers being different from the usual a common theme. It includes classical topics like analog computing, computing using different types of computing devices like optical computing, DNA computing, solition-based computing (where a solition is a robust solitary wave), or quantum computing. Other articles explore alternative paradigms like artificial chemistry, immunecomputing or aspects like nanocomputers or amorphous computing.

Wavelet transforms are useful tools that are often applied in image processing and statistical analysis. The section on ‘Wavelets’ contains a number of articles that cover the basics as well as advanced concepts and related tools like curvelets and ridgelets. Implementation details are discussed as well as applications in statistics and image processing.

The compendium was published in 2012 and consists of selections from the Encyclopedia of complexity and system sciences from 2009 [R. A. Meyers, (ed.), Encyclopedia of Complexity and System Sciences. 11 Volumes. New York, NY: Springer (2009; Zbl 1171.93001)]. It covers a modern, lively aspect of science and, therefore, at places the age shows, in particular in but not restricted to the references.

The work is more than 3500 pages long and comes in six volumes. The table of contents contains page numbers and remains silent about volume numbers, making navigation unnecessary tedious. The articles are sorted alphabetically with respect to their titles so that if a title is known it can be found without the help of the table of contents equally fast.

There are 209 articles and since they are sorted alphabetically with respect to the titles they range from ‘Additive cellular automata’ by Burton Voorhees to ‘Zero-sum two person games’ by T. E. S. Raghavan. Some of the subjects are covered in great detail, e. g., there are 29 articles about cellular automata, 11 articles about quantum computing, 10 articles about social networks, and 8 articles about granular computing in a narrow sense. The 209 articles are organized in 14 sections, 13 of which come with an introduction. They have varying numbers of articles (and, consequently, varying levels of detail), and each of the 14 different sections is in the editorial responsibility of one of the 13 section editors. More precisely:

– Agent based modeling and simulation (14 articles), edited by Filippo Castiglione;

– Mathematical basis of cellular automata (29 articles), edited by Andrew Adamatzky;

– Complex networks and graph theory (14 articles), edited by Geoffrey Canright;

– Data mining and knowledge discovery (10 articles), edited by Peter Kokol;

– Game theory (28 articles), edited by Marilda Sotomayor;

– Granular computing (23 articles), edited by Tsau Y. Lin;

– Intelligent systems (6 articles), edited by James A. Hendler;

– Probability and statistics in complex systems (18 articles), edited by Hendrik Jeldtoft Jensen;

– Quantum information science (9 articles), edited by Joseph F. Traub;

– Social network analysis (11 articles), edited by John Scott;

– Physics and mathematics applications in social science (3 articles), edited by Andrzej Nowak;

– Soft computing (12 articles), edited by Janusz Kacprzyk;

– Unconventional computing (21 articles), edited by Andrew Adamatzky;

– Wavelets (11 articles), edited by Edward Aboufadel.

These 13 section editors peer-reviewed the articles of their sections (with the help of the main editor Robert A. Meyers and the board members Richard E. Stearns, Stephen Wolfram, and Lotfi A. Zadeh) and have selected articles for inclusion. This procedure is supposed to assure ‘that the reader can have a level of confidence in the relevance and accuracy of the information exceeding that generally found on the World Wide Web’ (preface, page VI, contained in each volume). Clearly, this applies to the time of the first publication in 2009.

The 13 section editors are from five different countries, namely the USA (4 editors), the UK (3 editors), Poland (2 editors), and one from each of Brazil, Italy, Norway, and Slovenia. The authors of the 209 articles come from 33 different countries and their geographical distribution reflects to some degree that of the section editors, the most common countries being the USA (100 authors), the UK (25 authors), France (19 authors), Poland (17 authors), Canada (15 authors), Germany (14 authors), Italy (13 authors), Israel (11 authors), Slovenia (10 authors), Spain (10 authors), and all other countries with less than 9 authors (where a single author may be counted for more than one country if he or she listed more than one affiliation).

All articles start with a miniature table of contents (called article outline), a glossary, and a definition of the subject. The glossary contains short definitions of the article’s central terms. The ‘Definition of subject’ explains what the article is about and usually also contains a motivation. Since many central topics are covered in numerous articles one finds the definition of some central terms in many glossaries. Since the glossaries have different authors these definitions differ. This clearly is very different from what one would expect to find in an encyclopedia but it is not necessarily a bad thing. Instead of a single definitive definition one can find numerous attempts at definitions, using different wordings and having different emphasis.

The articles contain concise descriptions, usually with precise statements including formal definitions and theorems. They come with a large number of figures, many of them in color. In general, they do not contain proofs but pointer to relevant literature instead. All articles (with the exception of most section introductions) contain a list of references. Many have in addition to this a list of books and reviews containing a more detailed and in-depth study of the article’s subject.

Homogeneity is restricted to the format of the articles, in the writing one finds all variety in style, degree of formality, and focus that one can expect from an edited volume. This independence of the authors is a strength since it allows central topics to be discussed from quite different perspectives. It is also a weakness since there are no references between the articles (apart from the section introductions). Where an article mentions the central topic of another article it is up to the reader to make this connection and find out where he or she can find more details.

Naturally, the articles reflect who their authors are. For articles with a very broad subject this can be a disadvantage. E. g., the article ‘Stochastic processes’ by Alan J. McKane (from the section ‘Probability and statistics in complex systems’) restricts its attention mostly to Markov chains and is clearly written from the perspective of physics. Even the list of books and reviews that contains [N. Wax et al., Selected papers on noise and stochastic processes. New York: Dover Publications (1954; Zbl 0059.11903)] as its only entry completely ignores the enormous body of mathematical treatments of the subject. On the other hand, when articles have a narrower focus and are written by one of the leading experts in the field, they are very useful, see ‘Immunecomputing’ by Jon Timmis for an excellent example.

The sheer size of the work makes an index highly desirable. There is indeed a lengthy index spanning 75 pages. Since the vast majority of the index terms comes with exactly one page number its usefulness is limited. More useful is the list of glossary terms with page numbers (but again without volume numbers) that on 18 pages contains all terms defined in any of the 197 glossaries.

With the exception of the section on ‘Physics and mathematics applications in social science’ each section comes with a (sometimes brief) overview article authored by the section editor. In most cases these articles can be recognized by having ‘Introduction to <section title>’ as their title. There are, however, exceptions to this rule (in the sections ‘Complex networks and graph theory’ and ‘Social network analysis’). These introductions provide a useful overview and pointers to the different articles of the section. Since the compendium is sorted alphabetically by title and not organized by sections these introductions are a bit hidden. It is worth the effort to look out for them.

The section on ‘Agent based modeling and simulation’ contains articles introducing and discussing this computational modeling paradigm including definitions, mathematical, and logical foundations. Other articles discuss implementation aspects on different levels. The section considers connections to artificial life, cellular automata, physics, computational economics, swarm intelligence, robotics, and games in some detail. Moreover, it contains articles concerned with applications, namely modeling of tumor invasion and for social phenomena simulation.

The section on ‘Mathematical basis of cellular automata’ contains detailed articles about many different foundational aspects of cellular automata, including their definition and categorization. Their is an emphasis on cellular automata in non-standard settings, i. e., different from the orthogonal grid. Several articles are devoted to the study of the dynamic behavior of cellular automata, including one article solely about gliders. Specific variants are discussed in their own articles, considering additive cellular automata, cellular automata with memory, quantum cellular automata, reversible cellular automata, structurally dynamic cellular automata, respectively. The articles dealing with mathematical foundations in a more narrow sense consider universality, group theoretic aspects, connections to algorithmic complexity and language theory, tiling problems, the firing squad synchronization problem, as well as cellular automata as models of parallel computation. There are also articles dealing with more application-oriented aspects like modeling of physical systems and growth phenomena including resulting effects like phase transitions and self-organized criticality.

The section on ‘Complex networks and graph theory’ contains articles laying groundwork by introducing classical concepts and results about random graphs and directed graphs, respectively. Several articles discuss specific examples for complex networks including food networks, gene regulatory networks, human sexual networks, internet topology, and the world wide web. More general or abstract concepts are also considered, e. g., growth models and motifs. In addition, one article is devoted to the subject of visualization of complex networks.

The section on ‘Data mining and knowledge discovery’ covers the role of artificial neural networks, case based reasoning, and rough sets in this area. Decision trees and ensemble methods are discussed. Two articles deal with dimensionality reduction. Attention is also paid to knowledge discovery. One article discusses the role evolutionary algorithms can play and contains a decent introduction to evolutionary algorithm that, however, is very cursory on the theory side and does not even touch the topic of computational complexity.

The section on ‘Game theory’ contains a number of articles that present clear and accessible descriptions of the different types of games, namely cooperative games, zero-sum two player games, stochastic games, inspection games, differential games, static games and dynamic games. There is an emphasis on repeated games with articles covering repeated games with complete information, with incomplete information, and reputation effects. The subject is often treated from the perspective of economics, covering topics like mechanism design, implementation theory, cost sharing, fair division, strategic complexity in game theory, market games and clubs. Applications are also discussed, examples include voting, evolutionary game theory, networks and stability.

The section on ‘Granular computing’ contains introductory articles (including a rather philosophical discussion of the subject) as well as a number of articles that discuss the role granular computing has to play in interaction with data mining, fuzzy logic and control, rough set theory, grid and cloud computing, and social networks. This choice of topics implies overlaps with three other sections, namely the section on ‘Data mining and knowledge discovery’, ‘Social network analysis’, and ‘Soft computing’, where fuzzy logic and rough sets are treated. Since there granular computing is not a topic this overlap actually is an advantage for the treatment of granular computing since an independent view on the same topics is available.

Intelligent systems is a research area that has huge overlaps with the topics of other sections. Consequently, the section on ‘Intelligent systems’ contains in some sense the leftovers, five articles on different aspects of intelligent systems that would not fit anywhere else. These are about learning and planning, mobile agents, and applications of intelligent systems in the areas of control, modeling, simulation, and the semantic web. It comes as a natural consequence of its topic that the section on ‘Probability and statistics in complex systems’ contains articles of a more abstract and fundamental level than most of the other sections. The section covers modeling of complex systems, phenomenology, and analysis of data from complex systems. Some of the articles have some tendency to favor a point of view that stems from physics. On the other hand the section contains overview articles on modern mathematical tools that either have the proven ability or potential to be extremely useful in dealing with complex systems. Examples include random walks, branching processes, correlations, entropy, extreme value statistics, random matrix theory, and stochastic LĂ¶wner evolution.

The section on ‘Quantum information science’ provides an overview of the major areas in quantum computing. It covers quantum algorithms, quantum computational complexity as well as quantum complexity for continuous problems. Moreover, it contains articles about implementation aspects, i. e., quantum computing with trapped ions, quantum computing using optics and quantum error correction, and finally a classic application area, quantum cryptography.

It may be a bit surprising to find a complete section on ‘Social network analysis’ in a computer science book since the research area originated in the social sciences. The articles in this section cover graph theoretical approaches, various modeling and analytical approaches and include one article about the visualization of social networks.

The section on ‘Physics and mathematics applications in social science’ contains only three articles (and no introduction). One article covers a simple adaptive multi-agent model of financial markets, called minority game, that has drawn considerable attention since its introduction in 1997 [D. Challet and Y.-C. Zhang, “Emergence of cooperation and organization in an evolutionary game”, Physica A 246, 407–418 (1997)]. The article describes the original setting and many variants, various analytical approaches and applications. Another article gives a broad overview of different models and theories about rational, goal-oriented agents. The third article provides an overview of different simulation models for social processes.

Soft computing is usually used as an umbrella term that covers the research areas of artificial neural networks, evolutionary computation (and, possibly, even broader nature-inspired computing), and fuzzy logic. The section on ‘Soft computing’ here narrows the term down to fuzzy logic and its applications only. The articles in this section cover the basics of fuzzy logic and fuzzy operators, rough sets and possibility theory, fuzzy optimization, as well as hybrid systems, including neuro-fuzzy systems.

The section on ‘Unconventional computing’ covers a very diverse set of approaches to computing that lack a common theme unless one considers being different from the usual a common theme. It includes classical topics like analog computing, computing using different types of computing devices like optical computing, DNA computing, solition-based computing (where a solition is a robust solitary wave), or quantum computing. Other articles explore alternative paradigms like artificial chemistry, immunecomputing or aspects like nanocomputers or amorphous computing.

Wavelet transforms are useful tools that are often applied in image processing and statistical analysis. The section on ‘Wavelets’ contains a number of articles that cover the basics as well as advanced concepts and related tools like curvelets and ridgelets. Implementation details are discussed as well as applications in statistics and image processing.

Reviewer: Thomas Jansen (Aberystwyth)

##### MSC:

68-00 | General reference works (handbooks, dictionaries, bibliographies, etc.) pertaining to computer science |

68-02 | Research exposition (monographs, survey articles) pertaining to computer science |

68Q01 | General topics in the theory of computing |

68Q25 | Analysis of algorithms and problem complexity |