Search
Search Results
-
Martin–Löf reducibility and cost functions
Martin-Löf (ML)-reducibility compares the complexity of K -trivial sets of natural numbers by examining the Martin-Löf random sequences that compute...
-
Computable Reducibility for Computable Linear Orders of Type ω
We study computable reducibility for computable isomorphic copies of the standard ordering of natural numbers. Following Andrews and Sorbi, we...
-
Reducibility for a Class of Two Dimensional Almost Periodic System with Quintic Real Polynomial
This paper focuses on the reducibility of almost periodic system with quintic real polynomials. Using the KAM iterative method, the perturbed system...
-
KL-Randomness and Effective Dimension Under Strong Reducibility
We show that the (truth-table) Medvedev degree KLR of Kolmogorov–Loveland randomness coincides with that of Martin-Löf randomness, MLR, answering a...
-
A Group-Theoretic Approach to the Reducibility Problem of Optimal Processes
The reducibility problem of optimal processes is posed, and a group-theoretic approach to its solution is proposed. This approach is based on the...
-
Quantitative behavior of unipotent flows and an effective avoidance principle
We give an effective bound on how much time orbits of a unipotent group U on an arithmetic quotient G /Γ can stay near homogeneous subvarieties of G /Γ...
-
Enumerating Classes of Effective Quasi-Polish Spaces
We discuss ideal presentations of effective quasi-Polish spaces and some of their subclasses. Based on this, we introduce and study natural...
-
Topological reducibilities for discontinuous functions and their structures
In this article, we give a full description of the topological many-one degree structure of real-valued functions, recently introduced by...
-
Variations of Statement, Variations of Strength. The Case of the Rival–Sands Theorems
The paper surveys results obtained mainly by the author with A. Marcone, P. Shafer, and G. Soldà centered around two theorems due to I. Rival and B....
-
Non-collapse of the Effective Wadge Hierarchy
We study the recently suggested effective Wadge hierarchy in effective spaces, concentrating on the non-collapse property. Along with hierarchies of...
-
Structures of Degrees of Negative Representations of Linear Orders
The structures of partially ordered sets of degrees of negative and positive representability of linear orders are studied. The focus is on the...
-
Reducibility for a fast-driven linear Klein–Gordon equation
We prove a reducibility result for a linear Klein–Gordon equation with a quasi-periodic driving on a compact interval with Dirichlet boundary...
-
The Great Debate
Forty+ years later, the controversy surrounding the Appel and Haken proof is amazingly alive and well. Even when the extraordinary in many respects...
-
On Universal Pairs in the Ershov Hierarchy
We develop the Ershov theory of C-classes for some finite families of sets in the Ershov hierarchy. We generalize the result by Muchnik on multiple
... -
Boole vs Wadge: Comparing Two Basic Tools of Descriptive Set Theory
We systematically compare \(\omega \) -Boolean classes and...
-
Computable Structure Theory of Partial Combinatory Algebras
We discuss the complexity of the class of countable partial combinatory algebras, coded as c.e. sets. We prove a completeness result, and also...
-
The Complexity of Finding Supergraphs
We consider several variations of the following problem: fix a countable graph G. Is an input graph H a(n induced) subgraph of G? If yes, can we find...