Optimal heuristic algorithms for the image of an injective function

The existence of optimal algorithms is not known for any decision problem in NP \ 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 the randomized and deterministic settings (a heuristic alg...

Full description

Saved in:
Bibliographic Details
Published in:Journal of mathematical sciences (New York, N.Y.) N.Y.), 2013, Vol.188 (1), p.7-16
Main Authors: Hirsch, E. A., Itsykson, D. M., Nikolaenko, V. O., Smal, A. V.
Format: Article
Language:English
Subjects:
Algorithms
Bibliography
Mathematics
Mathematics and Statistics
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The existence of optimal algorithms is not known for any decision problem in NP \ 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 the randomized and deterministic settings (a heuristic algorithm may err on a small fraction 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. Bibliography: 12 titles.
ISSN:1072-3374
1573-8795
DOI:10.1007/s10958-012-1102-y