Computational Complexity: Theory, Techniques, and Applications
Format: PDF / Kindle (mobi) / ePub
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.
applications are only at their beginnings and much more are expected in the future. For example, in view of the results of Subsect. “Example 1”, we wonder if Kolmogorov complexity can help in proving the famous conjecture that languages recognizable in real time by CA are a strict subclass of linear-time recognizable languages (see [9,14]). Another completely diﬀerent development would consist in ﬁnding how and if Theorem 11 extends to higher dimensions. How this property can be restated in the
Materio Immunecomputing Mechanical Computing: The Computational Complexity of Physical Devices Membrane Computing Molecular Automata Nanocomputers Optical Computing Quantum Computing Reaction-Diﬀusion Computing Reversible Computing Thermodynamics of Computation Unconventional Computing, Introduction to Unconventional Computing, Novel Hardware for Wavelets, Section Editor: Edward Aboufadel Bivariate (Two-dimensional) Wavelets Comparison of Discrete and Continuous Wavelet Transforms Curvelets and
volatile than the fundamental value. Following Shiller’s methodology we deﬁne the detrended price, p, and fundamental value, p f . Averaging over 100 independent simulations we ﬁnd (p) D 27:1 and (p f ) D 19:2, which is an excess volatility of 41% . Heavy Volume As investors in our model have diﬀerent information (the informed investors know the dividend process, while the EMB investors do not), and diﬀerent ways of interpreting the information (EMB investors with diﬀerent memory spans have
which to simulate large numbers of agents. Some suggestions are listed in Table 1. The simplest solution to enable larger scale agent simulation is usually to improve the computer hardware that is used and run the model on a server or invest in a more 77 78 Agent Based Modeling, Large Scale Simulations Agent Based Modeling, Large Scale Simulations, Table 1 Potential solutions to implement when faced with a large number of agents to model Solution Reduce the number of agents in order for model
f n ) : k n n !k : That is, we consider systems for which the coordinate functions f i are linear, resp. aﬃne, polynomials. (In the Boolean case this includes functions constructed from XOR (sum modulo 2) and negation.) When each f i is a linear polynomial of the form f i (x1 ; : : : ; x n ) D a i1 x1 C C a i n x n , the map ˚ is nothing but a linear transformation on kn over k, and, by using the standard basis, ˚ has the matrix representation 02 31 2 32 3 x1 a11 x1 a1n B6 7C 6 :: 7 6 :: 7 ;