Asymptotic density and computability

I. I. Batyrshin

Izvestiâ vysših učebnyh zavedenij. Matematika, no. 10 (2021), pp. 3-14.

Résumé

We show that a set is bi-immune if and only if there are no computable permutations that arrange the set into a generically computable set or an effectively densely computable set. An example of a coarsely computable bi-immune set is constructed. It is also proved that for any set there is a permutation from the same Turing degree that arranges the set into an effectively densely computable set. The upper densities of some sets are studied.

Détail

Keywords: asymptotic density, generic complexity, Turing degree.
Mots-clés : bi-immune set

Bibliographie

[1] Novikov P. S., “Ob algoritmicheskoi nerazreshimosti problemy tozhdestva slov v teorii grupp”, Tr. MIAN SSSR, 44, 1955, 3–143

[2] Boone W. W., “The world problem”, Ann. Math., 70:2 (1959), 207–265 | DOI | Zbl

[3] Markov A. A., “Nerazreshimost problemy gomeomorfii”, DAN SSSR, 121:2 (1958), 218–220 | Zbl

[4] Matiyasevich Yu. V., “Diofantovost perechislimykh mnozhestv”, DAN SSSR, 191:2 (1970), 279–282 | Zbl

[5] Cook S. A., “The complexity of theorem-proving procedures”, Proc. Third Annual ACM Symposium on Theory of Comput., 1971, 151–158 | DOI | Zbl

[6] Levin L. A., “Universalnye zadachi perebora”, Probl. peredachi informatsii, 9:3 (1973), 115–116 | Zbl

[7] Karp R. M., “Reducibility among Combinatorial Problems”, Complexity of Computer Computations, Plenum Press, New York, 1972, 85–103 | DOI | Zbl

[8] Levin L., “Average case complete problems”, SIAM J. Comput., 1986, no. 15, 285–286 | DOI | Zbl

[9] Spielman D. A., Teng S., “Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time”, J. ACM, 51:3 (2004), 385–463 | DOI | Zbl

[10] Erdös P., “On the asymptotic density of the sum of two sequences one of which forms a basis for the integers, II”, Tr. Tbilissk. matem. in-ta, 3 (1938), 217–223 | Zbl

[11] Erdös P., “On the asymptotic density of the sum of two sequences”, Ann. Math., 43:1 (1942), 65–68 | DOI | Zbl

[12] Gromov M., “Hyperbolic groups”, Essays in Group Theory, MSRI ser., 8, ed. Gertsen S. M., Springer-Verlag, Berlin, 1987, 75–263

[13] Ol'shanskii A.Yu., “Almost every group is hyperbolic”, Internat. J. Algebra Comput., 2 (1992), 1–17 | DOI | Zbl

[14] Champetier C., “Petite simplification dans les groupes hyperboliques”, Ann. Fac. Sci. Toulouse Math., 3:2 (1994), 161–221 | DOI | Zbl

[15] Kapovich I., Myasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264 (2003), 665–694 | DOI | Zbl

[16] Jockusch C. G., Schupp P. E., “Generic computability, Turing degrees, and asymptotic density”, J. London Math. Soc., 85:2 (2012), 472–490 | DOI | Zbl

[17] Downey R. G., Jockusch C. G., Schupp P. E., “Asymptotic density and computably enumerable sets”, J. Math. Logic, 13:2 (2013), 1–43 | DOI

[18] Igusa G., “Nonexistence of minimal pairs for generic computability”, J. Symbolic Logic, 78:2 (2013), 511–522 | DOI | Zbl

[19] Bienvenu L., Day A., Hölzl R., “From bi-immunity to absolute undecidability”, J. Symbolic Logic, 17:4 (2013), 1218–1228 | DOI

[20] Igusa G., “The generic degrees of density-1 sets and a characterization of the hyper-arithmetic reals”, J. Symbolic Logic, 80:4 (2015), 1290–1314 | DOI | Zbl

[21] Downey R. G., Jockusch C. G., McNicholl T. H., Schupp P. E., “Asymptotic density and the Ershov Hierarchy”, Math. Log. Quarterly, 61:3 (2015), 189–195 | DOI | Zbl

[22] Astor E., “Asymptotic density, immunity, and randomness”, Computability, 4:2 (2015), 141–158 | DOI | Zbl

[23] Hirschfeldt D. R., Jockusch C. G., McNicholl T. H., Schupp P. E., “Asymptotic density and the coarse computability bound”, Computability, 5:1 (2016), 13–27 | DOI | Zbl

[24] Andrews U., Cai M., Diamondstone D., Jockusch C. G., Lempp S., “Asymptotic density, computable traceability, and $1$-randomness”, Fundamenta Math., 234:1 (2016), 41–53 | Zbl

[25] Dzhafarov D. D., Igusa G., “Notions of robust information coding”, Computability, 6:2 (2017), 105–124 | DOI | Zbl

[26] Hirschfeldt D. R., Jockusch C. G., Kuyper R., Schupp P. E., “Coarse reducibility and algorithmic randomness”, J. Symbolic Logic, 81:3 (2016), 1028–1046 | DOI | Zbl

[27] Cholak P., Igusa G., “Density-$1$ bounding and quasiminimality in the generic degrees”, J. Symbolic Logic, 82:3 (2017), 931–957 | DOI | Zbl

[28] Astor E., Hirschfeldt D. R., Jockusch C. G., “Dense computability, upper cones and minimal pairs”, Computability, 8:2 (2019), 155–177 | DOI | Zbl

[29] Harrison-Trainor M., “The Gamma questions for many-one degrees”, Ann. Pure and Appl. Logic, 168:7 (2017), 1396–1405 | DOI | Zbl

[30] Monin B., “An answer to the Gamma question”, Proc. 33rd Annual IEEE Symposium on LICS, LICS 2018, 2018, 730–738 | Zbl

[31] Monin B., Nies A., “A unifying approach to the Gamma question”, Proc. 30th Annual ACM/IEEE Symposium on LICS, LICS 2015, 2015, 585–596 | Zbl

[32] Jockusch C. G., Schupp P. E., “Asymptotic density and the theory of computability: A partial survey”, Computability and Complexity, Lect. Notes in Computer Sci., eds. Adam Day, Michael Fellows, Noam Greenberg, Bakhadyr Khoussainov, Alexander Melnikov, Frances Rosamond, Springer, 2017, 501–520 | DOI | Zbl

[33] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni, Kazansk. matem. o-vo, Kazan, 2000

[34] Ershov Yu. L., “Ob odnoi ierarkhii mnozhestv, I”, Algebra i logika, 7:1 (1968), 47–75

[35] Ershov Yu. L., “Ob odnoi ierarkhii mnozhestv, II”, Algebra i logika, 7:4 (1968), 15–48

[36] Ershov Yu. L., “Ob odnoi ierarkhii mnozhestv, III”, Algebra i logika, 9:1 (1970), 34–52

[37] Myasnikov A., Rybalov A., “Generic complexity of undecidable problems”, J. Symbolic Logic, 73 (2008), 656–673 | DOI | Zbl

[38] Kurtz S. A., “Notions of weak genericity”, J. Symbolic Logic, 48 (1983), 764–770 | DOI | Zbl