Geodesic
Generically undecidable and hard problems
Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 109-116.

Voir la notice de l'article provenant de la source Math-Net.Ru

The generic-case approach to algorithmic problems examines the behavior of an algorithm on typical (almost all) inputs and ignores the rest of the inputs. The method of generic amplification was proposed by A. Myasnikov and author for constructing of generically undecidable problems. The main ingredient of this method is the cloning technique, which combines the input data of a problem into sufficiently large sets of equivalent input data. Equivalence is understood in the sense that the problem is solved in the same way for them. We present a generalization of this method. We also construct a problem that is decidable in the classical sense, but which is not generically decidable in polynomial time. We use a different method to generic amplification, because generic amplification is unlikely to be applicable here.
Keywords: generic complexity, amplyfication, algorithmic problems. 
@article{PDM_2024_1_a7,
     author = {A. N. Rybalov},
     title = {Generically undecidable and hard problems},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {109--116},
     publisher = {mathdoc},
     number = {1},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2024_1_a7/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - Generically undecidable and hard problems
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2024
SP  - 109
EP  - 116
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2024_1_a7/
LA  - ru
ID  - PDM_2024_1_a7
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T Generically undecidable and hard problems
%J Prikladnaâ diskretnaâ matematika
%D 2024
%P 109-116
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2024_1_a7/
%G ru
%F PDM_2024_1_a7
A. N. Rybalov. Generically undecidable and hard problems. Prikladnaâ diskretnaâ matematika, no. 1 (2024), pp. 109-116. http://geodesic.mathdoc.fr/item/PDM_2024_1_a7/

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

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

[3] Rybalov A., “On the generic undecidability of the Halting Problem for normalized Turing machines”, Theory of Computing Systems, 60:4 (2017), 671–676 | DOI | MR | Zbl

[4] Rybalov A. N., “On the generic complexity of elementary theories”, Vestnik OmSU, 2015, no. 4, 14–17 (in Russian)

[5] Rybalov A., “Generic complexity of the Diophantine problem”, Groups Complexity Cryptology, 5:1 (2013), 25–30 | DOI | MR | Zbl

[6] Rybalov A., “Generic complexity of Presburger arithmetic”, Theory of Computing Systems, 46:1 (2010), 2–8 | DOI | MR | Zbl

[7] Hirschfeldt D., “Some questions in computable mathematics”, LNCS, 10010, 2017, 22–55 | MR | Zbl

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

[9] Gilman A., Myasnikov A., and Roman'kov V. A., “Random equations in free groups”, Groups Complexity Cryptology, 3:2 (2011), 257–284 | DOI | MR | Zbl

[10] Gilman A., Myasnikov A., and Roman'kov V. A., “Random equations in nilpotent groups”, J. Algebra, 352:1 (2012), 192–214 | DOI | MR | Zbl