In the talk we consider subrecursive algebraic structures. One of the key notions in this direction is the notion of a punctual structure introduced by Kalimullin, Melnikov, and Ng (2017). An infinite algebraic structure S is punctual if the domain of S is equal to the set of natural numbers, and the signature functions and relations of the structure S are primitive recursive. The methods of...
We shall be concerned with a natural one-sorted language L for talking about probability spaces, where quantifiers are intended to range over events in a given space. In this language one can express statements like `for every event E, if P(E) > 0, then there exists an event F such that 0 < P(F) < P(E)' — here P denotes the measure in question. It is known that the validity problem for...
The problem of recursion elimination is a broad topic, including purely mathematical as well as practical formulations. Mathematical formulation may be presented as follows: What are decidable sufficient conditions to find a primitive recursive function that is equivalent to a given recursive function. A practical formulation, for instance, may be presented as follows: what are syntactic...
We consider some questions related to the problem of searching a structure A computable in polynomial time (in short, P-computable), which is isomorphic to a given abstract structure B. In particular, a general criterion for the existence of such a P-computable structure B is formulated. As an application, we discuss some questions about the existence of P-computable presentations for a series...
The proof system resolution over parities (Res(⊕)) operates with disjunctions of linear equations (linear clauses) over GF(2); it extends the resolution proof system by incorporating linear algebra over GF(2). Over the years, several exponential lower bounds on the size of tree-like Res(⊕) refutations have been established. However, proving a superpolynomial lower bound on the size of...
We give a survey of algorithmic complexity results for theories of algebraic structures including Kleene star. Those include Kleene algebras, Kleene lattices, and their extensions with division operations, also called action algebras / lattices. We focus on equational and Horn theories, since already on this level of expressivity we get high levels of undecidability. The talk includes both...
In this talk we discuss the exact real computation paradigm, which turns into practice the rigorous but theoretical computable analysis approach (see, e.g., [Weihrauch 2000]). We also highlight some of its recent applications in computing solutions of differential equations with guaranteed prescribed precision. Exact real computation packages allow to conveniently implement imperative...
The monotone minimal perfect hash (MMPH) is a data structure that, for a set of n integers k1<...<kn from an interval [1..u], supports the following queries: given x, the query either returns i such that ki = x if such i exists, or returns any number otherwise. The MMPH is a well-known algorithmic workhorse with many applications, both theoretical and practical. The most space-efficient known...
One of the most famous algorithms in quantum computations is the Grover search algorithm. Under certain assumptions, this algorithm provides quantum speedup for the search problem. We always assume that we can build it efficiently, but assume for a moment that you are limited in the gates you are allowed to use for the implementation of the Grover diffusion operator. For example, if you need...
