The complexity of identifying redundant and essential elements

In many optimization problems a solution is a subset of optimum number of elements satisfying some desired property. An element is redundant if it does not belong to any solution of the problem. An element is essential if it belongs to every solution of the problem. We consider the complexity of indentifying redundant and essential elements in a sample of NP-Hard optimization problems. It is shown that these identification problems are also NP-Hard. The proofs are based on an analysis of the original reductions of Cook [The complexity of theorem proving procedures, in “Proceedings, Third Annual Assoc. Comput. Mach. Symposium on Theory of Computing”, pp. 151–158, Assoc. Comput. Mach., New York 1971] and Karp [Reducibility among combinational problems, in “Complexity of Computer Computations” (R. E. Miller and J. W. Thatcher, Eds.), pp. 85–104, Plenum, New York 1972].     

A reaction-diffusion system with cross-diffusion modeling the spread of an epidemic disease

We provide existence results for nonnegative solutions to a class of reaction-diffusion systems with cross-diffusion modeling the spread of an epidemic disease. The existence of weak solutions is proved by means of an approximation process, the Faedo-Galerkin method, and a compactness argument. Under additional assumptions a global existence result for classical solutions is derived upon using interpolation results between Banach spaces.     

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.     

An extension of the dual complexity space and an application to Computer Science

In 1999, Romaguera and Schellekens introduced the theory of dual complexity spaces as a part of the development of a mathematical (topological) foundation for the complexity analysis of programs and algorithms [S. Romaguera, M.P. Schellekens, Quasi-metric properties of complexity spaces, Topology Appl. 98 (1999) 311-322]. In this work we extend the theory of dual complexity spaces to the case that the complexity functions are valued on an ordered normed monoid. We show that the complexity space of an ordered normed monoid inherits the ordered normed structure. Moreover, the order structure allows us to prove some topological and quasi-metric properties of the new dual complexity spaces. In particular, we show that these complexity spaces are, under certain conditions, Hausdorff and satisfy a kind of completeness. Finally, we develop a connection of our new approach with Interval Analysis.     

Unifications,deunifications, and their complexity

The execution of a Prolog program can be viewed as a sequence of unifications and backtracks over unifications. We study the time requirement of executing a sequence of such operations (the unify-deunify problem). It is shown that the well-known set union problem is reducible to this problem, even in the case when no function symbols are allowed (the Datalog unify-deunify problem). As the set union problem requires nonlinear time on a large class of algorithms, the same holds for the unify-deunify problem. Thus the linearity of single unifications does not give a complete picture of the time complexity of Prolog primitives. We discuss the methods for executing sequences of Datalog unifications used in Prolog interpreters and show that some of them require even quadratic time in the worst case. Complementing these results, we show that if the number of variables occurring in one clause is bounded by a constant, then the Datalog unify-deunify problem can be solved in linear time.A preliminary version of this paper appeared in the Third International Conference on Logic Programming, London, July 1986. This work was supported by the Academy of Finland and by TEKES.     

Communication, complexity, and evolutionary stability

In games with costless preplay communication, some strategies are more complex than others in the sense that they induce a finer partition of the set of states of the world. This paper shows that if the concept of evolutionary stability, which is argued to be a natural solution concept for communication games, is modified to take lexicographic complexity preferences into account, then for a class of games of common interest only communication strategies that induce payoff-dominant Nash outcomes of the underlying game are stable. Received April 1998/Final version September 1998     

Equi-invariability,bounded invariance complexity and L-stability for control systems

In this paper, we introduce the notions of bounded invariance complexity, bounded invariance complexity in the mean and mean Lyapunov-stability for control systems. Then we characterize these notions by introducing six types of equi-invariability. As a by-product, two new dichotomy theorems for the control system on the control sets are established.     

A derivative concept with respect to an arbitrary kernel and applications to fractional calculus

In this paper, we propose a new concept of derivative with respect to an arbitrary kernel function. Several properties related to this new operator, like inversion rules and integration by parts, are studied. In particular, we introduce the notion of conjugate kernels, which will be useful to guaranty that the proposed derivative operator admits a right inverse. The proposed concept includes as special cases Riemann‐Liouville fractional derivatives, Hadamard fractional derivatives, and many other fractional operators. Moreover, using our concept, new fractional operators involving certain special functions are introduced, and some of their properties are studied. Finally, an existence result for a boundary value problem involving the introduced derivative operator is proved.     

Topological complexity, fibrations and symmetry

We show how locally smooth actions of compact Lie groups on a manifold X can be used to obtain new upper bounds for the topological complexity TC(X), in the sense of Farber. We also obtain new bounds for the topological complexity of finitely generated torsion-free nilpotent groups.     

A note on the complexity of an algorithm for chebyshev approximation

Some remarks are given concerning the complexity of an exchange algorithm for Chebyshev Approximation.Dedicated to Germund Dahlquist on the occasion of his 60th birthday.Supported in part by NIH Grant RR01243 at the University of Washington. — The paper was revised at the Naval Postgraduate School, Monterey, California.     

Sensitivity to complexity—an important prerequisite of problem solving mathematics teaching

Teaching is deciding and acting in a complex system. If a teacher attempts to fulfil demands to teach mathematics with a stronger problem solving orientation, it becomes even more complex. This complexity must not be reduced arbitrarily. Instead, a sufficient degree of sensitivity is necessary to competently and flexibly deal with emerging demands on the teacher. In this article I provide an introduction to the concept of sensitivity to complexity of mathematics teaching and report on specific realistic and interactive diagnostic instruments. A particular focus is placed on a diagnostic interview about decision-making situations which could occur in a mathematics lesson. A first pilot study with student teachers from different German universities—briefly outlined in the last part of this article—suggests its suitability for gaining important indications of the agent's degree of sensitivity to complexity of problem solving mathematics teaching.     

Gap in the essential spectrum of the Neumann problem for an elliptic system in a periodic domain

We establish the existence of a gap in the essential spectrum of the Neumann problem for an elliptic formally self-adjoint system of second-order differential equations on a quasi-cylinder (a domain with periodically varying cross-section).     

Isotonic tests for spread and tail

Summary One-sample test problem for ‘stochastically more (or less) spread’ is defined and a family of tests with isotonic power is given. The problem is closely related to that for ‘longer (or shorter) tail’ in the reliability theory and the correspondence between them is shown. To characterize the tests three spread preorders inR ⁿ and corre-sponding tail preorders inR ₊ ⁿ are introduced. Functions which are ‘monotone’ in these orders, and subsets which are ‘centrifugal’ or ‘centripetal’ with respect to these orders are studied. These notions generalize the Schur convexity. The Institute of Statistical Mathematics