RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2012 Volume 399, Pages 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

Abstract: The existence of optimal algorithms is not known for any decision problem in $\mathbf{NP}\setminus\mathbf{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 randomized and deterministic settings (a heuristic algorithm can err on a small fraction $\frac1d$ 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.

Key words and phrases: optimal algorithm, heuristic algorithm.

UDC: 510.52

Received: 31.07.2011

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2013, 188:1, 7–16

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024