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
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - يناير 2013
منشور خارجيًانعم

All Science Journal Classification (ASJC) codes

  • !!Applied Mathematics
  • !!Statistics and Probability
  • !!General Mathematics

بصمة

أدرس بدقة موضوعات البحث “Optimal heuristic algorithms for the image of an injective function'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا