Suboptimality and complexity in evolution

A scalable model of biological evolution is presented which includes energy cost for building new elements and multiple paths for obtaining new functions. The model allows a population with a continual increase of complexity, but as time passes, detrimental mutations accumulate. This model shows the crucial importance of accounting for the energy cost of new structures in models of biological evolution. © 2014 Wiley Periodicals, Inc. Complexity 21: 322–327, 2015     

Instability,complexity, and evolution

In this paper, we consider a new class of random dynamical systems that contains, in particular, neural networks and complicated circuits. For these systems, we consider the viability problem: we suppose that the system survives only the system state is in a prescribed domain Π of the phase space. The approach developed here is based on some fundamental ideas proposed by A. Kolmogorov, R. Thom, M. Gromov, L. Valiant, L. Van Valen, and others. Under some conditions it is shown that almost all systems from this class with fixed parameters are unstable in the following sense: the probability P _t to leave Π within the time interval [0, t] tends to 1 as t → ∞. However, it is allowed to change these parameters sometimes (“evolutionary” case), then it may happen that P _t  < 1 − δ  < 1 for all t (“stable evolution”). Furthermore, we study the properties of such a stable evolution assuming that the system parameters are encoded by a dicsrete code. This allows us to apply complexity theory, coding, algorithms, etc. Evolution is a Markov process of modification of this code. Under some conditions we show that the stable evolution of unstable systems possesses the following general fundamental property: the relative Kolmogorov complexity of the code cannot be bounded by a constant as t → ∞. For circuit models, we define complexity characteristics of these circuits. We find that these complexities also have a tendency to increase during stable evolution. We give concrete examples of stable evolution. Bibliography: 80 titles. To the memory of A. N. Livshitz Published in Zapiski Nauchnykh Seminarov POMI, Vol. 360, 2008, pp. 31–69.     

Exploring the evolution of complexity in signaling networks

Signaling networks are exemplified by systems as diverse as biological cells, economic markets, and the Web. After a discussion of some general characteristics of signaling networks, this article explores the adaptive evolution of complexity in a simple model of a signaling network. The article closes with a discussion of broader questions concerning the evolution of signaling networks. © 2002 Wiley Periodicals, Inc.     

Some regularities in human group formation and the evolution of societal complexity

The emerging science of complexity suggests that Darwinian theory alone may not provide a complete explanation for the evolution of complexity. In this paper human social systems are compared to sparsely connected K = 2 networks where order emerges from the restriction of interactions among elements. The organization of human systems both resembles and differs from the behavior of K = 2 networks. The differences derive, it is suggested, from the evolutionary history of the human information processing system. © 2001 John Wiley & Sons, Inc.     

Asymptotic Simplicity and Static Data

The present article considers time-symmetric initial data sets for the vacuum Einstein field equations, which are conformally related to static initial data sets in such a way that in a neighbourhood of infinity the two initial data sets have the same massless part. It is shown that for this class of data, the solutions to the regular finite initial value problem at spatial infinity for the conformal Einstein field equations extend smoothly through the critical sets where null infinity touches spatial infinity if and only if the initial data sets coincide with static data in a neighbourhood of infinity. This result highlights the special role played by static data among the class of initial data sets for the Einstein field equations whose development gives rise to a spacetime with a smooth conformal compactification at null infinity.     

Understanding and attenuating the complexity catastrophe in Kauffman's N K model of genome evolution

Kauffman's N K model—used for studying the performance of systems consisting of a finite number of components that interact with each other in complex ways—exhibits the complexity catastrophe, in which high levels of interaction in systems with a large number of components lead to a decrease in performance. It is shown here that the complexity catastrophe is a consequence of the mathematical assumptions underlying the N K model. Analysis and simulations are used to establish the idea that relaxing any one of these assumptions results in a new model in which the complexity catastrophe is attenuated. Thus, good performance from systems having high levels of interactions is possible. ©1999 John Wiley & Sons, Inc.     

Characterization of Simplicity and Cancellativity in βS

We determine precisely when the Stone-Cech compactification βS of a discrete semigroup S is simple and when it is left cancellative or right cancellative. As a consequence we see that βS is cancellative only when it is trivially so. That is, βS is cancellative if and only if S is a finite group.     

Simplicity of eigenvalues in Anderson-type models

We show almost sure simplicity of eigenvalues for several models of Anderson-type random Schrödinger operators, extending methods introduced by Simon for the discrete Anderson model. These methods work throughout the spectrum and are not restricted to the localization regime. We establish general criteria for the simplicity of eigenvalues which can be interpreted as separately excluding the absence of local and global symmetries, respectively. The criteria are applied to Anderson models with matrix-valued potential as well as with single-site potentials supported on a finite box.     

Simplicity and credibility: A counterstrategy

A counterstrategy to conventional strategies which increase technical complexity to achieve small gains in efficiency and power is to trade of ‘bestness’ for simplicity. In public issues (e.g., neonatal hypothyroidism at Three Mile Island) simplicity enhances credibility.     

Sets of Commuting Derivations and Simplicity

A ring R is simple under a set D of derivations if no nontrivial ideal of R is preserved by all derivations in D. Continuing previous joint work with C. J. Maxson, the author provides a computational test for the simplicity of k[x ₁,…,x _n ]/〈 x ₁ ^p ,…, x _n ^p 〉 (k a field of characteristic p > 0) under a set of commuting k-derivations. Specific rings are then examined for sets of commuting derivations, especially those under which the ring is simple. The possible sizes and minimality of such sets are also determined in particular cases.     

Local and Subquotient Inheritance of Simplicity in Jordan Systems

In this paper we prove that the local algebras of a simple Jordan pair are simple. Jordan pairs all of which local algebras are simple are also studied, showing that they have a nonzero simple heart, which is described in terms of powers of the original pair. Similar results are given for Jordan triple systems and algebras. Finally, we characterize the inner ideals of a simple pair which determine simple subquotients, answering the question posed by O. Loos and E. Neher (1994, J. Algebra166, 255–295).     

Simplicity and superrigidity of twin building lattices

Kac–Moody groups over finite fields are finitely generated groups. Most of them can naturally be viewed as irreducible lattices in products of two closed automorphism groups of non-positively curved twinned buildings: those are the most important (but not the only) examples of twin building lattices. We prove that these lattices are simple if the corresponding buildings are irreducible and not of affine type (i.e. they are not Bruhat–Tits buildings). Many of them are finitely presented and enjoy property (T). Our arguments explain geometrically why simplicity fails to hold only for affine Kac–Moody groups. Moreover we prove that a nontrivial continuous homomorphism from a completed Kac–Moody group is always proper. We also show that Kac–Moody lattices fulfill conditions implying strong superrigidity properties for isometric actions on non-positively curved metric spaces. Most results apply to the general class of twin building lattices. Dedicated to Jacques Tits with our admiration     

Simplicity of noncommutative Dedekind domains

The following dichotomy is established: A finitely generated, complex Dedekind domain that is not commutative is a simple ring. Weaker versions of this dichotomy are proved for Dedekind prime rings and hereditary noetherian prime rings.

     

The Parallel Simplicity of Compaction and Chaining

Given a set of values x₁, x₂,..., x_n, of which k are nonzero, the compaction problem is the problem of moving the nonzero elements into the first k consecutive memory locations. The chaining problem asks that the nonzero elements be put into a linked list. One can in addition require that the elements remain in the same order, leading to the problems of ordered compaction and ordered chaining, respectively. This paper introduces a technique involving perfect hash functions that leads to a deterministic algorithm for ordered compaction running on a CRCW PRAM in time O(log k/log log n) using n processors. A matching lower bound for unordered compaction is given. The ordered chaining problem is shown to be solvable in time O(α(k)) with n processors (where α is a functional inverse of Ackermann′s function) and unordered chaining is shown to he solvable in constant time with n processors when k < n^{1/4− ε}.