اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNoise vs computational intractability in dynamics
45
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that describes a natural process. The first one is unaccounted-for errors, which may make the system unpredictable beyond a very limited time horizon. This is especially true for chaotic systems, where a small change in the initial conditions may cause a dramatic shift in the trajectories. The second one is Turing-completeness. By the undecidability of the Halting Problem, the long-term prospects of a system that can simulate a Turing Machine cannot be determined computationally. We investigate the interplay between these two forces -- unaccounted-for errors and Turing-completeness. We show that the introduction of even a small amount of noise into a dynamical system is sufficient to destroy Turing-completeness, and to make the systems long-term behavior computationally predictable. On a more technical level, we deal with long-term statistical properties of dynamical systems, as described by invariant measures. We show that while there are simple dynamical systems for which the invariant measures are non-computable, perturbing such systems makes the invariant measures efficiently computable. Thus, noise that makes the short term behavior of the system harder to predict, may make its long term statistical behavior computationally tractable. We also obtain some insight into the computational complexity of predicting systems affected by random noise.
قيم البحث
اقرأ أيضاً
The central conjecture of parameterized complexity states that FPT is not equal to W[1], and is generally regarded as the parameterized counterpart to P != NP. We revisit the issue of the plausibility of FPT != W[1], focusing on two aspects: the diff
iculty of proving the conjecture (assuming it holds), and how the relation between the two classes might differ from the one between P and NP. Regarding the first aspect, we give new evidence that separating FPT from W[1] would be considerably harder than doing the same for P and NP. Our main result regarding the relation between FPT and W[1] states that the closure of W[1] under relativization with FPT-oracles is precisely the class W[P], implying that either FPT is not low for W[1], or the W-Hierarchy collapses. This theorem also has consequences for the A-Hierarchy (a parameterized version of the Polynomial Hierarchy), namely that unless W[P] is a subset of some level A[t], there are structural differences between the A-Hierarchy and the Polynomial Hierarchy. We also prove that under the unlikely assumption that W[P] collapses to W[1] in a specific way, the collapse of any two consecutive levels of the A-Hierarchy implies the collapse of the entire hierarchy to a finite level; this extends a result of Chen, Flum, and Grohe (2005). Finally, we give weak (oracle-based) evidence that the inclusion of W[t] in A[t] is strict for t>1, and that the W-Hierarchy is proper. The latter result answers a question of Downey and Fellows (1993).
We consider the motion of a finite though large number $N$ of hard spheres in the whole space $mathbb{R}^n$. Particles move freely until they experience elastic collisions. We use our recent theory of Compensated Integrability in order to estimate ho
w much the particles are deviated by collisions. Our result, which is expressed in terms of hodographs, tells us that only $O(N^2)$ collisions are significant.
We develop a framework to study the role of variability in transport across a streamline of a reference flow. Two complementary schemes are presented: a graphical approach for individual cases, and an analytical approach for general properties. The s
patially nonlinear interaction of dynamic variability and the reference flow results in flux variability. The characteristic time-scale of the dynamic variability and the length-scale of the flux variability in a unit of flight-time govern the spatio-temporal interaction that leads to transport. The non-dimensional ratio of the two characteristic scales is shown to be a a critical parameter. The pseudo-lobe sequence along the reference streamline describes spatial coherency and temporal evolution of transport. For finite-time transport from an initial time up to the present, the characteristic length-scale of the flux variability regulates the width of the pseudo-lobes. The phase speed of pseudo-lobe propagation averages the reference flow and the flux variability. In contrast, for definite transport over a fixed time interval and spatial segment, the characteristic time-scale of the dynamic variability regulates the width of the pseudo-lobes. Generation of the pseudo-lobe sequence appears to be synchronous with the dynamic variability, although it propagates with the reference flow. In either case, the critical characteristic ratio is found to be one, corresponding to a resonance of the flux variability with the reference flow. Using a kinematic model, we demonstrate the framework for two types of transport in a blocked flow of the mid-latitude atmosphere: across the meandering jet axis and between the jet and recirculating cell.
We present a mathematical analysis of a networks with Integrate-and-Fire neurons and adaptive conductances. Taking into account the realistic fact that the spike time is only known within some textit{finite} precision, we propose a model where spikes
are effective at times multiple of a characteristic time scale $delta$, where $delta$ can be textit{arbitrary} small (in particular, well beyond the numerical precision). We make a complete mathematical characterization of the model-dynamics and obtain the following results. The asymptotic dynamics is composed by finitely many stable periodic orbits, whose number and period can be arbitrary large and can diverge in a region of the synaptic weights space, traditionally called the edge of chaos, a notion mathematically well defined in the present paper. Furthermore, except at the edge of chaos, there is a one-to-one correspondence between the membrane potential trajectories and the raster plot. This shows that the neural code is entirely in the spikes in this case. As a key tool, we introduce an order parameter, easy to compute numerically, and closely related to a natural notion of entropy, providing a relevant characterization of the computational capabilities of the network. This allows us to compare the computational capabilities of leaky and Integrate-and-Fire models and conductance based models. The present study considers networks with constant input, and without time-dependent plasticity, but the framework has been designed for both extensions.
We derive the equations of motion for the dynamics of a porous media filled with an incompressible fluid. We use a variational approach with a Lagrangian written as the sum of terms representing the kinetic and potential energy of the elastic matrix,
and the kinetic energy of the fluid, coupled through the constraint of incompressibility. As an illustration of the method, the equations of motion for both the elastic matrix and the fluid are derived in the spatial (Eulerian) frame. Such an approach is of relevance e.g. for biological problems, such as sponges in water, where the elastic porous media is highly flexible and the motion of the fluid has a primary role in the motion of the whole system. We then analyze the linearized equations of motion describing the propagation of waves through the media. In particular, we derive the propagation of S-waves and P-waves in an isotropic media. We also analyze the stability criteria for the wave equations and show that they are equivalent to the physicality conditions of the elastic matrix. Finally, we show that the celebrated Biots equations for waves in porous media are obtained for certain values of parameters in our models.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
