اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPunctual equivalence relations and their (punctual) complexity
109
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations $R$ and $S$ on natural numbers, $R$ is computably reducible to $S$ if there is a computable function $f colon omega to omega$ that induces an injective map from $R$-equivalence classes to $S$-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. In this work, we explore $mathbf{Peq}$, the degree structure generated by primitive recursive reducibility on punctual equivalence relations (i.e., primitive recursive equivalence relations with domain $omega$). In contrast with all other known degree structures on equivalence relations, we show that $mathbf{Peq}$ has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of $mathbf{Peq}$, proving, e.g., that the structure is neither rigid nor homogeneous.
قيم البحث
اقرأ أيضاً
Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibil
ity. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility spectrum of computably enumerable equivalence relations with no countable basis and a reducibility spectrum of computably enumerable equivalence relations which is downward dense, thus has no basis.
In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root with a prescribed multiplicity structure. More precisely, given a polynomial system f $=(f_1, ldots, f_N)in C[x_1, ldots, x_n]^N$, we presen
t a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of $f$ such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so called inverse system that describes the multiplicity structure at the root. We use $$alpha$$-theory test to certify the quadratic convergence, and togive bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria.
We study the class of Borel equivalence relations under continuous reducibility. In particular , we characterize when a Borel equivalence relation with countable equivalence classes is $Sigma$ 0 $xi$ (or $Pi$ 0 $xi$). We characterize when all the equ
ivalence classes of such a relation are $Sigma$ 0 $xi$ (or $Pi$ 0 $xi$). We prove analogous results for the Borel equivalence relations with countably many equivalence classes. We also completely solve these two problems for the first two ranks. In order to do this, we prove some extensions of the Louveau-Saint Raymond theorem which itself generalized the Hurewicz theorem characterizing when a Borel subset of a Polish space is G $delta$ .
We study certain DT invariants arising from stable coherent sheaves in a nonsingular projective threefold supported on the members of a linear system of a fixed line bundle. When the canonical bundle of the threefold satisfies certain positivity cond
itions, we relate the DT invariants to Carlsson-Okounkov formulas for the twisted Eulers number of the punctual Hilbert schemes of nonsingular surfaces, and conclude they have a modular property.
We study strong types and Galois groups in model theory from a topological and descriptive-set-theoretical point of view, leaning heavily on topological dynamical tools. More precisely, we give an abstract (not model theoretic) treatment of problems
related to cardinality and Borel cardinality of strong types, quotients of definable groups and related objecets, generalising (and often improving) essentially all hitherto known results in this area. In particular, we show that under reasonable assumptions, strong type spaces are locally quotients of compact Polish groups. It follows that they are smooth if and only if they are type-definable, and that a quotient of a type-definable group by an analytic subgroup is either finite or of cardinality at least continuum.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
