Abstract: 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.

Cite: Рыбалов А.Н.
Генерически неразрешимые и трудноразрешимые проблемы
Прикладная дискретная математика (Prikladnaya Diskretnaya Matematika). 2024. №63. С.109-116. DOI: 10.17223/20710410/63/7 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Oct 24, 2023
Accepted:	Nov 14, 2023
Published print:	Mar 1, 2024
Published online:	Mar 1, 2024

Identifiers:

Web of science:	WOS:001245342000008
Scopus:	2-s2.0-85192247050
Elibrary:	63427023
OpenAlex:	W4402849300

Citing:

DB	Citing
Elibrary	2
Scopus	1
Web of science	1
OpenAlex	1

Altmetrics: