Complexity of Equivalence Relations and Preorders from Computability Theory
We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relations R, S, a componentwise reducibility is defined by
R ≤ S ⇔ ∃f ∀x, y [x R y ↔ f (x) S f (y)].
Here, f is taken from a suitable class of effective functions. For us the relations will be on natural numbers, and f must be computable. We show that there is a -complete equivalence relation, but no -complete for k ≥ 2. We show that preorders arising naturally in the above-mentioned areas are -complete. This includes polynomial time m-reducibility on exponential time sets, which is , almost inclusion on r.e. sets, which is , and Turing reducibility on r.e. sets, which is .
It is known that the normalized algorithmic information distance is not computable and not semicomputable. We show that for all 𝜀<1/2, there exist no semicomputable functions that differ from N by at most 𝜀. Moreover, for any computable function f such that |lim𝑡𝑓(𝑥,𝑦,𝑡)−N(𝑥,𝑦)|≤𝜀 and for all n, there exist strings x, y of length n such that
∑_𝑡 |𝑓(𝑥,𝑦,𝑡+1)−𝑓(𝑥,𝑦,𝑡)| ≥ 𝛺(log 𝑛)
This is optimal up to constant factors.
We also show that the maximal number of oscillations of a limit approximation of N is 𝛺(𝑛/log𝑛). This strengthens the 𝜔(1) lower bound from [K. Ambos-Spies, W. Merkle, and S.A. Terwijn, 2019, Normalized information distance and the oscillation hierarchy].
We consider a scalar fast differential equation which is periodically driven by a slowly varying input. Assuming that the equation depends on scalar parameters, we present simple sufficient conditions for the existence of a periodic canard solution, which, within a period, makes n fast transitions between the stable branch and the unstable branch of the folded critical curve. The closed trace of the canard solution on the plane of the slow input variable and the fast phase variable has n portions elongated along the unstable branch of the critical curve. We show that the length of these portions and the length of the time intervals of the slow motion separated by the short time intervals of fast transitions between the branches are controlled by the parameters.
The paper is the obituary of Alexei V. Pokrovskii (02.06.1948 - 01.09.2010), this volume of the journal was dedicated to Alexei Pokrovskii.
We consider certain spaces of functions on the circle, which naturally appear in harmonic analysis, and superposition operators on these spaces. We study the following question: which functions have the property that each their superposition with a homeomorphism of the circle belongs to a given space? We also study the multidimensional case.
We consider the spaces of functions on the m-dimensional torus, whose Fourier transform is p -summable. We obtain estimates for the norms of the exponential functions deformed by a C1 -smooth phase. The results generalize to the multidimensional case the one-dimensional results obtained by the author earlier in “Quantitative estimates in the Beurling—Helson theorem”, Sbornik: Mathematics, 201:12 (2010), 1811 – 1836.
We consider the spaces of function on the circle whose Fourier transform is p-summable. We obtain estimates for the norms of exponential functions deformed by a C1 -smooth phase.
This proceedings publication is a compilation of selected contributions from the “Third International Conference on the Dynamics of Information Systems” which took place at the University of Florida, Gainesville, February 16–18, 2011. The purpose of this conference was to bring together scientists and engineers from industry, government, and academia in order to exchange new discoveries and results in a broad range of topics relevant to the theory and practice of dynamics of information systems. Dynamics of Information Systems: Mathematical Foundation presents state-of-the art research and is intended for graduate students and researchers interested in some of the most recent discoveries in information theory and dynamical systems. Scientists in other disciplines may also benefit from the applications of new developments to their own area of study.