Geodesic
Optimal heuristic algorithms for the image of an injective function
Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 15-31 
E. A. Hirsch; D. M. Itsykson; V. O. Nikolaenko; A. V. Smal. Optimal heuristic algorithms for the image of an injective function. Zapiski Nauchnykh Seminarov POMI, Computational complexity theory. Part X, Tome 399 (2012), pp. 15-31. http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a1/
@article{ZNSL_2012_399_a1,
     author = {E. A. Hirsch and D. M. Itsykson and V. O. Nikolaenko and A. V. Smal},
     title = {Optimal heuristic algorithms for the image of an injective function},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {15--31},
     year = {2012},
     volume = {399},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a1/}
}
TY  - JOUR
AU  - E. A. Hirsch
AU  - D. M. Itsykson
AU  - V. O. Nikolaenko
AU  - A. V. Smal
TI  - Optimal heuristic algorithms for the image of an injective function
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2012
SP  - 15
EP  - 31
VL  - 399
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a1/
LA  - en
ID  - ZNSL_2012_399_a1
ER  - 
%0 Journal Article
%A E. A. Hirsch
%A D. M. Itsykson
%A V. O. Nikolaenko
%A A. V. Smal
%T Optimal heuristic algorithms for the image of an injective function
%J Zapiski Nauchnykh Seminarov POMI
%D 2012
%P 15-31
%V 399
%U http://geodesic.mathdoc.fr/item/ZNSL_2012_399_a1/
%G en
%F ZNSL_2012_399_a1

Voir la notice du chapitre de livre provenant de la source Math-Net.Ru

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.

[1] A. Bogdanov, L. Trevisan, “Average-case complexity”, Foundation and Trends in Theoretical Computer Science, 2:1 (2006), 1–106 | DOI | MR

[2] Y. Chen, J. Flum, M. Müller, “Hard instances of algorithms and proof systems”, Electronic Colloquium on Computational Complexity, 2011, 11-085 | MR

[3] O. Goldreich, Foundation of Cryptography: Basic Tools, Cambridge University Press, 1995 | MR

[4] O. Goldreich, A. Wigderson, “Tiny families of functions with random properties: A quality-size trade-off for hashing”, Random Structures Algorithms, 11:4 (1997), 315–343 | 3.0.CO;2-1 class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[5] E. A. Hirsch, D. Itsykson, I. Monakov, A. Smal, “On optimal heuristic randomized semidecision procedures, with applications to proof complexity and cryptography”, Theory of Computing Systems, 2012 (to appear)

[6] E. A. Hirsch, “Optimal acceptors and optimal proof systems”, TAMC, Lect. Notes Computer Sci., 6108, 2010, 28–39 | DOI | MR | Zbl

[7] J. Krajíček, P. Pudlák, “Propositional proof systems, the consistency of first order theories and the complexity of computations”, J. Symbolic Logic, 54:3 (1989), 1063–1079 | DOI | MR | Zbl

[8] L. A. Levin, “Universal sequential search problems”, Problems Information Transmission, 9 (1973), 265–266 | MR

[9] C. McDiarmid, “Concentration”, Algorithms Combinatorics, 16, Springer-Verlag, 1998, 195–248 | DOI | MR | Zbl

[10] J. Messner, “On optimal algorithms and optimal proof systems”, Proceedings of the 16th Symposium on Theoretical Aspects of Computer Science, Lect. Notes Computer Sci., 1563, 1999, 361–372 | MR

[11] H. Monroe, “Speedup for natural problems and noncomputability”, Theor. Computer Sci., 412:4–5 (2011), 478–481 | DOI | MR | Zbl

[12] Z. Sadowski, “On an optimal deterministic algorithm for SAT”, Proceedings of CSL' 98, Lect. Notes Computer Sci., 1584, Springer, 1999, 179-187 | DOI | MR | Zbl