|
Записки научных семинаров ПОМИ, 2012, том 399, страницы 15–31
(Mi znsl5219)
|
|
|
|
Optimal heuristic algorithms for the image of an injective function
[Оптимальные эвристические алгоритмы для образа инъективной функции]
E. A. Hirscha, D. M. Itsyksona, V. O. Nikolaenkob, A. V. Smala a St. Petersburg Department of the Steklov Mathematical Institute, St. Petersburg, Russia
b St. Petersburg Academic University, St. Petersburg, Russia
Аннотация:
К настоящему моменту ни для какого языка из $\mathbf{NP}\setminus\mathbf{P}$ не известно оптимального алгоритма для задачи его распознавания. В данной статье рассматривается задача проверки принадлежности образу инъективной функции. Предложена конструкция эвристического алгоритма для этой задачи в вероятностном и в детерминированном случаях (эвристический алгоритм может ошибаться на небольшой доле $\frac1d$ всех входов; параметр $d$ также передаётся алгоритму). Для данной задачи это улучшает раннее предложенную конструкцию оптимального вероятностного эвристического аксептора (который является оптимальным только на дополнении языка). Библ. – 12 назв.
Ключевые слова:
оптимальный алгоритм, эвристический алгоритм.
Поступило: 31.07.2011
Образец цитирования:
E. A. Hirsch, D. M. Itsykson, V. O. Nikolaenko, A. V. Smal, “Optimal heuristic algorithms for the image of an injective function”, Теория сложности вычислений. X, Зап. научн. сем. ПОМИ, 399, ПОМИ, СПб., 2012, 15–31; J. Math. Sci. (N. Y.), 188:1 (2013), 7–16
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl5219 https://www.mathnet.ru/rus/znsl/v399/p15
|
Статистика просмотров: |
Страница аннотации: | 126 | PDF полного текста: | 41 | Список литературы: | 23 |
|