כבר כמה שנים יש אלגוריתמים הסתברותים מאוד טובים
למשימה זאת.
ובאוגוסט פיתחו בהודו שיטה דטרמיניסטית
פולינומיאלית באורך הקלט בינתיים הם עובדים בסדר גודל
של חזקת 12 שזה הרבה יותר גרוע מהפתרון ההסתברותי,
אבל זה יתן פתרון שנכון ב100% ולא ב 99.9999999% כפי
שמקובל באלגוריתמים ההסתברותיים.בינתיים למשימות מעשיות אנשים מעדיפים להישאר הספק
(הקלוש מאוד, קלוש כרצוננו) של הפתרונות ההסתברותיים.
המדענים בהודו טוענים שהם ישפרו את הסיבוכיות לסדר
גודל של בהחזקת 6.
DRYICE
נ.ב הסדרי גודל הם לא ביחס למספר אלה ביחס לאורך הייצוג הבינארי
שלו שזה לוגריתם של המספר. מכאן הפתרונות שראינו לעיל
הם כולם אקספוננציאלים לפי אורך המספר.