Optimal heuristic algorithms for the image of an injective function

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