ECCC-Report TR11-091https://eccc.weizmann.ac.il/report/2011/091Comments and Revisions published for TR11-091en-usFri, 10 Jun 2011 17:07:44 +0300
Paper TR11-091
| Optimal heuristic algorithms for the image of an injective function |
Edward Hirsch,
Dmitry Itsykson,
Valeria Nikolaenko,
Alexander Smal
https://eccc.weizmann.ac.il/report/2011/091The existence of optimal algorithms is not known for any decision problem in NP$\setminus$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 1/d 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.
Fri, 10 Jun 2011 17:07:44 +0300https://eccc.weizmann.ac.il/report/2011/091