Optimal heuristic algorithms for the image of an injective function

E. A. Hirsch, D. M. Itsykson, V. O. Nikolaenko, A. V. Smal

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

תקציר

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 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. Bibliography: 12 titles.

שפה מקוריתאנגלית
עמודים (מ-עד)7-16
מספר עמודים10
כתב עתJournal of Mathematical Sciences
כרך188
מספר גיליון1
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - ינו׳ 2013
פורסם באופן חיצוניכן

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2604???
  • ???subjectarea.asjc.2600.2613???
  • ???subjectarea.asjc.2600.2600???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Optimal heuristic algorithms for the image of an injective function'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי