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

===זמן ריצה תת -מעריכי===

סיבוכיות זמן ריצה תת -מעריכית או תת -אקספוננציאלית, מוערכת על ידי <math>\ L_n[\alpha,c]</math>, כאשר:

בעיית פירוק לגורמים נחשבה במשך שנים לבעייהלבעיה אקספוננציאלית והיא עמדה על סיבוכיות משוערת מסדר גודל <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>. בכל המקרים נוסחאות הסיבוכיות מנומקות, מוסכמות על כל המומחים, מגובות בתוצאות אמפיריות - אך אינן [[הוכחה|מוכחות]].