Generically undecidable and hard problems | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2024. № 63. DOI: 10.17223/20710410/63/7

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.