Victor Selivanov, Effective Wadge hierarchy in computable quasi-Polish spaces

The Wadge hierarchy was originally defined and studied only in the Baire space. We extend it here to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g. several Hausdorff-Kuratowski-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder. We also develop effective versions of the aforementioned results in computable quasi-Polish spaces which include most spaces of interest for computable analysis.

Svetlana Selivanova, Bit-complexity of computing solutions of linear hyperbolic partial differential equations with guaranteed precision

In this talk we discuss motivation, recent progress and perspectives of classifying partial differential equations (PDEs) according to their algorithmic complexity. We mainly focus on the case of linear hyperbolic systems as a broad subclass, including the wave equation and many other practically important equations of mathematical physics. In all of the results, the solution is computed with arbitrary guaranteed prescribed precision.

We establish upper bounds on bit complexity of computing solution operators for symmetric hyperbolic systems of PDEs, combining symbolic and approximate algorithms to obtain the solutions with guaranteed prescribed precision. Restricting to algebraic real inputs allows us to use the classical (“discrete”) bit complexity concept. We devise sufficient conditions for the solution operator to be PTIME/EXPTIME computable. Further, we study the case of primitive recursive input data, and establish primitive recursiveness of the solution operator under certain restrictions.

Using the Exact Real Computation approach, we establish PSPACE and #P complexity bounds of computing the solutions of linear evolutionary (including hyperbolic and parabolic) systems of PDEs, depending on hypotheses on the real-valued fixed PTIME computable initial data. For the case of analytic initial data we devise PTIME algorithms, which can be used in practical implementations.

The talk is based on joint works with Victor Selivanov; Ivan Koswara, Gleb Pogudin, Martin Ziegler; Florian Steinberg, Holger Thies.

Alexander Okhotin, Determinization of event-clock input-driven pushdown automata

Input-driven pushdown automata (also known as visibly pushdown automata and as nested word automata) are a subclass of deterministic pushdown automata and a superclass of the parenthesis languages. In 2009, Nguyen and Ogawa ("Event-clock visibly pushdown automata", SOFSEM 2009), introduced a variant of this model operating in real time under the event-clock model, in which the automaton can check the time elapsed since the last occurence of each symbol, as well as predict the time remaining until its next occurrence. Nguyen and Ogawa proved that these automata can be determinized, using the method of "region construction", under which the space of clock values is discretized, the automaton is accordingly untimed, determinized as an untimed model and then converted back to timed. In this work, a new, direct determinization construction is proposed: for a given n-state nondeterministic automaton with k different clock constraints and with any number of stack symbols, the resulting deterministic automaton uses 2^{n^2} states, 2^{n^2+k} stack symbols and the same clock constraints as in the original automaton. Furthermore, this construction is shown to be asymptotically optimal with respect to both the number of states and the number of stack symbols.

Joint work with Prof. Mizuhito Ogawa from JAIST.

Kenta Sasaki, A generalization of Louveau's separation theorem for Wadge classes of bqo-valued Borel functions

Louveau showed that if a Borel set in a Polish space happens to be in a Borel Wadge class Γ, then its Γ-code can be obtained from its Borel code in a hyperarithmetical manner. This is obtained as an easy corollary of a separation result for Borel Wadge class, and is applied to many problems in descriptive set theory since we can extract information about uniformity from non-uniform conditions. We extend this result to Wadge hierarchy of bqo-valued Borel functions on a Polish space. This has become possible due to the complete analysis of Wadge degrees of bqo-valued Borel functions by the recent work of Kihara-Montalbán.

Ruslan Kornev, Degrees of metrics under computable reducibility

Let X be a Polish topological space with a distinguished countable dense subset. Then we can study a notion of computable reducibility of metrics on X that is induced by computable reducibility of their respective Cauchy representations. The resulting degree structure is denoted by M_c(X), and the structure of degrees of computable metrics is denoted by CM_c(X). In the talk we discuss elementary properties of these orderings: existence of minimal and maximal elements and lattice properties.

Takako Nemoto, Determinacy of Wadge classes and subsystems of second order arithmetic

In [1], the class of games in second order arithmetic corresponding to Wadge classes are given and it was proved that the determinacy of such classes in low level of arithmetical hierarchy characterize almost all known subsystems of second order arithmetic. In this talk, we review the results in [1] and introduce several recent results.

[1] Takako Nemoto, Determinacy of Wadge classes and subsystems of second order arithmetic, Mathematical Logic Quarterly, Volume 55, Issue 2, February 2009, pp. 154 - 176.

Akitoshi Kawamura, Average-case polynomial-time computability of Hamiltonian dynamics

We apply average-case complexity theory to physical problems modeled by continuous-time dynamical systems. The computational complexity when simulating such systems for a bounded time-frame mainly stems from trajectories coming close to complex singularities of the system. We show that if for most initial values the trajectories do not come close to singularities the simulation can be done in polynomial time on average. For Hamiltonian systems we relate this to the volume of “almost singularities” in phase space and give some general criteria to show that a Hamiltonian system can be simulated efficiently on average. As an application we show that the planar circular-restricted three-body problem is average-case polynomial-time computable.

Joint work with Holger Thies and Martin Ziegler.

Ryoma Sin'ya, Measure theoretic approach to formal language theory

In [1], the speaker proposed a notion called REG-measurability, where REG is the class of all regular languages. Intuitively, a language L is REG-measurable if there exists an infinite sequence of regular languages that "converges" to L. A language without REG-measurability has a complex shape in some sense so that it can not be (asymptotically) approximated by regular languages. It has been shown that, while there are uncountably many REG-measurable languages (including complex context-free languages), certain deterministic context-free languages and the set of all primitive words are REG-immeasurable in a strong sense [1].

In this talk the speaker gives a summary of above results, and then introduces some new results on Carathéodory extensions of fragments of regular languages (local varieties of regular languages).

[1] Ryoma Sin’ya, “Asymptotic Approximation by Regular Languages”, SOFSEM 2021.

Takayuki Kihara, Around the Wadge rank ω_2

Kechris and Martin claimed that the Wadge rank of the ω-th level of the decreasing difference hierarchy of coanalytic sets is ω_2 under the axiom of determinacy. In this talk, we give an alternative proof of the Kechris-Martin theorem, by understanding the ω-th level of the decreasing difference hierarchy of coanalytic sets as the (relative) hyperarithmetical processes with finite mind-changes. Moreover, we give a negative answer to Fournier's question on the gap between the increasing and decreasing difference hierarchies of coanalytic sets by relating them to the Π^1_1- and Σ^1_1-least number principles, respectively. We also examine Weihrauch degrees of related principles.

Margarita Korovina, and Oleg Kudinov, Some properties of complexity classes over real numbers

It this talk we revile relations between a class of computable (recursive) functions K and a structure K* of real numbers induced by K. We propose natural restrictions on a class K under which the structure K* is a real closed field. We also investigate whether there exist computable copies of generated structures for popular classes of computable functions such as the polynomial time computable functions and the Grzegorczyk classes (staring from the second level). We establish that the corresponding structures do not have computable copies and, moreover, the polynomial time computable real numbers as a real closed field is not computably presentable.

Matthew de Brecht, Representing quasi-Polish spaces as spaces of ideals, with applications to computable topology

We present recent results on a characterization of quasi-Polish spaces as spaces of ideals of a transitive relation on a countable set, and investigate some applications of this characterization to computable topology. We also demonstrate how to construct the lower powerspace, upper powerspace, and space of valuations of a quasi-Polish space in terms of spaces of ideals, based on ideas from domain theory.

Keita Yokoyama, On the unique existence conservation theorem for WKL

It is well-known that if a singleton {x} in the Cantor space is Muchnik reducible to the set of all completions of PA, then x is computable. In [STY], Simpson/Tanaka/Yamazaki reformulated this idea in the setting of second-order arithmetic and showed that Weak Koenig's lemma (WKL) is conservative over RCA_0 with respect to the formulas of the form "for all X there exists unique Y such that A(X,Y)" for arithmetical A. This may be considered as a miniaturized version of the conservation result for AC over ZF by Carlson [Car] since WKL is equivalent to a very weak form of the axiom of choice. In this talk, we will sharpen the forcing argument used in [STY] and see when similar conservation results hold. Besides, we see the feasibility of those conservation results; namely, they are realized by polynomial proof-transformations.

[STY] S. G. Simpson, K. Tanaka and T. Yamazaki. Some conservation results on weak König's lemma. Ann. Pure Appl. Logic 118 (2002), 87–114.

[Car] T. J. Carlson. On the conservativity of the axiom of choice over set theory. Arc. Math. Logic 50 (2011), 777-790.