"Записки научных семинаров ПОМИ"

Том 399, стр. 15-31

Санкт-Петербургское отделение Математического института им. В. А. Стеклова РАН, Фонтанка 27, Санкт-Петербург 191023, Россия

СПбАУ НОЦНТ РАН, ул. Хлопина, д. 8, корпус 3, Санкт-Петербург 194021, Россия

Web: http://logic.pdmi.ras.ru~hirsch,~dmitrits,~smal

Аннотация:К настоящему моменту ни для какого {\it языка} из $\mathbf{NP}\setminus\mathbf{P}$ не известно оптимального алгоритма для задачи его распознавания. В данной статье рассматривается задача проверки принадлежности образу инъективной функции. Предложена конструкция \emph{эвристического} алгоритма для этой задачи в вероятностном и в детерминированном случаях (эвристический алгоритм может ошибаться на небольшой доле $\frac1d$ всех входов; параметр $d$ также передаётся алгоритму). Для данной задачи это улучшает раннее предложенную конструкцию оптимального вероятностного эвристического аксептора (который является оптимальным только на дополнении языка). Библ. -- 12 назв.
Ключевые слова: оптимальный алгоритм, эвристический алгоритм [optimal algorithm, heuristic algorithm]