סיבוכיות זמן – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
שורה 53:
בעיית ה[[פירוק מספר שלם לגורמים|פירוק של מספר שלם לגורמים]] נחשבה במשך שנים לבעיה אקספוננציאלית והיא עמדה על סיבוכיות משוערת מסדר גודל <math>\ L_n[1/2,c]</math> והושגו רק שיפורים מינוריים בערכו של הקבוע <math>\ c</math>. שיפור משמעותי הושג ב-[[1988]], כאשר המתמטיקאים [[ג'ון פולארד]], [[מארק מאנאס]], [[הנדריק לנסטרה]] ו[[ארג'ן לנסטרה]] פרסמו את שיטת [[נפת שדה מספרים]] המיוחדת לפירוק מספרים בעלי מבנה מיוחד כ[[מספר פרמה|מספרי פרמה]] ו[[מספרי קנינגהם]]. לשיטה זו סיבוכיות מהצורה <math>\ L_n[1/3,c]</math> כשהקבוע <math>\ c=(32/9)^{1/3}\approx1.526</math>. כמספר שנים לאחר מכן, פותח האלגוריתם הכללי - "נפת שדה המספרים הכללית" המתאים לפירוק כל מספר שלם ויעילותו מוערכת ב-<math>\ L_n[1/3,c]</math>, כשהקבוע <math>\ c=(64/9)^{1/3}\approx1.923</math>. בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות - אך אינן [[הוכחה|מוכחות]].
 
מומחים הראו שעל ידי [[אלגוריתם קוונטי]] המבוצע ב[[מחשב קוונטי]], כגון [[אלגוריתם שור]], ניתן להפחית את זמן הריצה של בעיית הפירוק לגורמים לזמן ריצה נמוךשל בהרבה<math>\ O(\log^3(n))</math> הנמוך משמעותית.
 
== ראו גם ==