Computational Complexity: Theory, Techniques, and Applications

Complex systems are systems that comprise many interacting parts with the ability to generate a new quality of collective behavior through self-organization, e.g. the spontaneous formation of temporal, spatial or functional structures.  These systems are often characterized by extreme sensitivity to initial conditions as well as emergent behavior that are not readily predictable or even completely deterministic.  The recognition that the collective behavior of the whole system cannot be simply inferred from an understanding of the behavior of the individual components has led to the development of numerous sophisticated new computational and modeling tools with applications to a wide range of scientific, engineering, and societal phenomena. Computational Complexity: Theory, Techniques and Applications presents a detailed and integrated view of the theoretical basis, computational methods, and state-of-the-art approaches to investigating and modeling of inherently difficult problems whose solution requires extensive resources approaching the practical limits of present-day computer systems.  This comprehensive and authoritative reference examines key components of computational complexity, including cellular automata, graph theory, data mining, granular computing, soft computing, wavelets, and more.

Table of Contents

Chapter 1. Additive Cellular Automata
Chapter 2. Agent Based Computational Economics
Chapter 3. Agent Based Modeling and Artificial Life
Chapter 4. Agent Based Modeling and Computer Languages
Chapter 5. Agent Based Modeling, Large Scale Simulations
Chapter 6. Agent Based Modeling, Mathematical Formalism for
Chapter 7. Agent Based Modeling and Simulation
Chapter 8. Agent Based Modeling and Simulation, Introduction to
Chapter 9. Aggregation Operators and Soft Computing
Chapter 10. Algorithmic Complexity and Cellular Automata
Chapter 11. AmorphousComputing
Chapter 12. Analog Computation
Chapter 13. ArtificialChemistry
Chapter 14. Artificial Intelligence in Modeling and Simulation
Chapter 15. Bacterial Computing
Chapter 16. Bayesian Games: Games with Incomplete Information
Chapter 17. Bayesian Statistics
Chapter 18. Bivariate (Two-dimensional) Wavelets
Chapter 19. Branching Processes
Chapter 20. Cellular Automata as Models of Parallel Computation
Chapter 21. Cellular Automata, Classification of
Chapter 22. Cellular Automata, Emergent Phenomena in
Chapter 23. Cellular Automata and Groups
Chapter 24. Cellular Automata in Hyperbolic Spaces
Chapter 25. Cellular Automata and Language Theory
Chapter 26. Cellular Automata with Memory
Chapter 27. Cellular Automata Modeling of Physical Systems
Chapter 28. Cellular Automata in Triangular, Pentagonal and Hexagonal Tessellations
Chapter 29. Cellular Automata, Universality of
Chapter 30. Cellular Automaton Modeling
Chapter 31. Cellular Computing
Chapter 32. Chaotic Behavior of Cellular Automata
Chapter 33. Community Structure in Graphs
Chapter 34. Comparison of Discrete and Continuous Wavelet Transforms
Chapter 35. Complex
Chapter 36. Complexity in Systems Level Biology and Genetics: Statistical Perspectives
Chapter 37. Complex Networks and Graph Theory
Chapter 38. Complex Networks, Visualization of
Chapter 39. Computer Graphics and Games, Agent Based Modeling in
Chapter 40. Computing in Geometrical Constrained Excitable Chemical Systems
Chapter 41. Computing with Solitons
Chapter 42. Cooperative Games
Chapter 43. Cooperative Games (Von Neumannâ•ÂfiMorgenstern Stable Sets)
Chapter 44. Cooperative Multi-hierarchical Query Answering Systems
Chapter 45. Correlated Equilibria and Communication in Games
Chapter 46. Correlations in Complex Systems
Chapter 47. Cost Sharing
Chapter 48. Curvelets and Ridgelets
Chapter 49. Data and Dimensionality Reduction in Data Analysis and System Modeling
Chapter 50. Data-Mining and Knowledge Discovery: Case-Based Reasoning, Nearest Neighbor and Rough Sets
Chapter 51. Data-Mining and Knowledge Discovery, Introduction to
Chapter 52. Data-Mining and Knowledge Discovery, Neural Networks in
Chapter 53. Decision Trees
Chapter 54. Dependency and Granularity inData
Chapter 55. Differential Games
Chapter 56. Discovery Systems
Chapter 57. DNA Computing
Chapter 58. Dynamic
Chapter 59. Dynamics of Cellular Automata in Non-compact Spaces
Chapter 60. Embodied and Situated Agents, Adaptive Behavior in
Chapter 61. Entropy
Chapter 62. Ergodic Theory of Cellular Automata
Chapter 63. Evolutionary Game Theory
Chapter 64. Evolution in Materio
Chapter 65. Evolving Cellular Automata
Chapter 66. Evolving Fuzzy Systems
Chapter 67. Extreme Value Statistics
Chapter 68. Fair Division *
Chapter 69. Field Theoretic Methods
Chapter 70. Firing Squad Synchronization Problem in Cellular Automata
Chapter 71. Fluctuations
Chapter 72. Food Webs
Chapter 73. Fuzzy Logic
Chapter 74. Fuzzy Logic, Type-2 and Uncertainty
Chapter 75. Fuzzy Optimization
Chapter 76. Fuzzy Probability Theory
Chapter 77. Fuzzy Sets Theory, Foundations of
Chapter 78. Fuzzy System Models
Chapter 79. Game Theory, Introduction to
Chapter 80. Game Theory and Strategic Complexity
Chapter 81. Genetic and Evolutionary Algorithms and Programming: General Introduction and Application to Game Playing
Chapter 82. Genetic-Fuzzy Data Mining Techniques
Chapter 83. Gliders in Cellular Automata
Chapter 84. Granular Computing and Data Mining for Ordered Data: The Dominance-Based Rough Set Approach
Chapter 85. Granular Computing, Information Models for
Chapter 86. Granular Computing, Introduction to
Chapter 87. Granular Computing and Modeling of the Uncertainty in Quantum Mechanics
Chapter 88. Granular Computing, Philosophical Foundation for
Chapter 89. Granular Computing: Practices, Theories, and Future Directions
Chapter 90. Granular Computing, Principles and Perspectives of
Chapter 91. Granular Computing System Vulnerabilities: Exploring the Dark Side of Social Networking Communities
Chapter 92. Granular Model for Data Mining
Chapter 93. Granular Neural Network
Chapter 94. Granulation of Knowledge: Similarity Based Approach in Information and Decision Systems
Chapter 95. Growth Models for Networks
Chapter 96. Growth Phenomena in Cellular Automata
Chapter 97. Hierarchical Dynamics
Chapter 98. Human Sexual Networks
Chapter 99. Hybrid Soft Computing Models for Systems Modeling and Control
Chapter 100. Identification of Cellular Automata
Chapter 101. Immunecomputing
Chapter 102. Implementation Theory
Chapter 103. Inspection Games
Chapter 104. Intelligent Control
Chapter 105. Intelligent Systems, Introduction to
Chapter 106. Interaction Based Computing in Physics
Chapter 107. Internet Topology
Chapter 108. Knowledge Discovery: Clustering
Chapter 109. Learning in Games
Chapter 110. Learning and Planning (Intelligent Systems)
Chapter 111. Levy Statistics and Anomalous Transport: Levy Flights and Subdiffusion
Chapter 112. Link Analysis and Web Search
Chapter 113. Logic and Geometry of Agents in Agent-Based Modeling
Chapter 114. Machine Learning, Ensemble Methods in
Chapter 115. Manipulating Data and Dimension Reduction Methods: Feature Selection
Chapter 116. Market Games and Clubs
Chapter 117. Mathematical Basis of Cellular Automata, Introduction to
Chapter 118. Mechanical Computing: The Computational Complexity of Physical Devices
Chapter 119. Mechanism Design
Chapter 120. Membrane Computing
Chapter 121. Minority Games
Chapter 122. Mobile Agents
Chapter 123. Molecular Automata
Chapter 124. Motifs
Chapter 125. Multi-Granular Computing and Quotient Structure
Chapter 126. Multivariate Splines and Their Applications
Chapter 127. Multiwavelets
Chapter 128. Nanocomputers
Chapter 129. Network Analysis, Longitudinal Methods of
Chapter 130. Networks and Stability
Chapter 131. Neuro-fuzzy Systems
Chapter 132. Non-negative Matrices and Digraphs
Chapter 133. Non-standard Analysis, an Invitation to
Chapter 134. Numerical Issues When Using Wavelets
Chapter 135. Optical Computing
Chapter 136. Phase Transitions in Cellular Automata
Chapter 137. Popular Wavelet Families and Filters and Their Use
Chapter 138. Positional Analysis and Blockmodeling
Chapter 139. Possibility Theory
Chapter 140. Principal-Agent Models
Chapter 141. Probability Densities in Complex Systems, Measuring
Chapter 142. Probability Distributions in Complex Systems
Chapter 143. Probability and Statistics in Complex Systems, Introduction to
Chapter 144. Quantum Algorithms
Chapter 145. Quantum Algorithms and Complexity for Continuous Problems
Chapter 146. Quantum Cellular Automata
Chapter 147. Quantum Computational Complexity
Chapter 148. Quantum Computing
Chapter 149. Quantum Computing with Trapped Ions
Chapter 150. Quantum Computing Using Optics
Chapter 151. Quantum Cryptography
Chapter 152. Quantum Error Correction and Fault Tolerant Quantum Computing
Chapter 153. Quantum Information Processing
Chapter 154. Quantum Information Science, Introduction to
Chapter 155. Random Graphs, a Whirlwind Tour of
Chapter 156. Random Matrix Theory
Chapter 157. Random Walks in Random Environment
Chapter 158. Rational, Goal-Oriented Agents
Chapter 159. Reaction-Diffusion Computing
Chapter 160. Record Statistics and Dynamics
Chapter 161. Repeated Games with Complete Information
Chapter 162. Repeated Games with Incomplete Information
Chapter 163. Reputation Effects
Chapter 164. Reversible Cellular Automata
Chapter 165. Reversible Computing
Chapter 166. Rough and Rough-Fuzzy Sets in Design of Information Systems
Chapter 167. Rough Set Data Analysis
Chapter 168. Rough Sets in Decision Making
Chapter 169. Rough Sets: Foundations and Perspectives
Chapter 170. Rule Induction, Missing Attribute Values and Discretization
Chapter 171. Self-organized Criticality and Cellular Automata
Chapter 172. Self-Replication and Cellular Automata
Chapter 173. Semantic Web
Chapter 174. Signaling Games
Chapter 175. Social Network Analysis, Estimation and Sampling in
Chapter 176. Social Network Analysis, Graph Theoretical Approaches to
Chapter 177. Social Network Analysis, Large-Scale
Chapter 178. Social Network Analysis, Overview of
Chapter 179. Social Network Analysis, Two-Mode Concepts in
Chapter 180. Social Networks, Algebraic Models for
Chapter 181. Social Networks, Diffusion Processes in
Chapter 182. Social Networks, Exponential Random Graph ( p * ) Models for
Chapter 183. Social Networks and Granular Computing
Chapter 184. Social Network Visualization, Methods of
Chapter 185. Social Phenomena Simulation
Chapter 186. Social Processes, Simulation Models of
Chapter 187. Soft Computing, Introduction to
Chapter 188. Static Games
Chapter 189. Statistical Applications of Wavelets
Chapter 190. Statistics with Imprecise Data
Chapter 191. Stochastic Games
Chapter 192. Stochastic Loewner Evolution: Linking Universality, Criticality and Conformal Invariance in Complex Systems
Chapter 193. Stochastic Processes
Chapter 194. Structurally Dynamic Cellular Automata
Chapter 195. Swarm Intelligence
Chapter 196. Synchronization Phenomena on Networks
Chapter 197. Thermodynamics of Computation
Chapter 198. Tiling Problem and Undecidability in Cellular Automata
Chapter 199. Topological Dynamics of Cellular Automata
Chapter 200. Two-Sided Matching Models
Chapter 201. Unconventional Computing, Introduction to
Chapter 202. Unconventional Computing, Novel Hardware for
Chapter 203. Voting
Chapter 204. Voting Procedures, Complexity of
Chapter 205. Wavelets, Introduction to
Chapter 206. Wavelets and the Lifting Scheme
Chapter 207. Wavelets and PDE Techniques in Image Processing, a Quick Tour of
Chapter 208. World Wide Web, Graph Structure
Chapter 209. Zero-Sum Two Person Games