Optimal heuristic algorithms for the image of an injective function

E. A. Hirsch, D. M. Itsykson, V. O. Nikolaenko, A. V. Smal

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

1 Цитирования (Scopus)

Аннотация

The existence of optimal algorithms is not known for any decision problem in NP \ P. We consider the problem of testing the membership in the image of an injective function. We construct optimal heuristic algorithms for this problem in both the randomized and deterministic settings (a heuristic algorithm may err on a small fraction 1/d of the inputs; the parameter d is given to it as an additional input.) Thus for this problem we improve an earlier construction of an optimal acceptor (that is optimal on the negative instances only) and also give a deterministic version. Bibliography: 12 titles.

Язык оригиналаанглийский
Страницы (с-по)7-16
Число страниц10
ЖурналJournal of Mathematical Sciences (United States)
Том188
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2013

Предметные области Scopus

  • Теория вероятности и статистика
  • Математика (все)
  • Прикладная математика

Fingerprint

Подробные сведения о темах исследования «Optimal heuristic algorithms for the image of an injective function». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать