Реферат: 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.

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

Даты:

Поступила в редакцию:	24 окт. 2023 г.
Принята к публикации:	14 нояб. 2023 г.
Опубликована в печати:	1 мар. 2024 г.
Опубликована online:	1 мар. 2024 г.

Идентификаторы БД:

Web of science:	WOS:001245342000008
Scopus:	2-s2.0-85192247050
РИНЦ:	63427023
OpenAlex:	W4402849300

Цитирование в БД:

БД	Цитирований
РИНЦ	2
Scopus	1
Web of science	1
OpenAlex	1

Альметрики: