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/