אלגוריתם דטרמיניסטי – הבדלי גרסאות

'''אלגוריתם דטרמיניסטי''' במדעי המחשב הוא [[אלגוריתם]] המתנהג בצורה צפויה וניתנת לניבוי. כלומר, בהינתן ‏‏[[קלט‏קלט]] מסוים, המכונה עליה רץ האלגוריתם לעולם תבצע את אותם צעדים והפלט הסופי לעולם יהיה אותו פלט.

כל ה[[מחשב|מחשבים]]ים המודרניים הם מחשבים דטרמיניסטיים, כלומר ניתן להריץ עליהם רק תוכנות המהוות יצוג של אלגוריתמים דטרמיניסטיים. בפרט, לא ניתן לחולל [[מספרים אקראיים]] באמצעות תוכנת מחשב. המספרים בהם משתמשים במחשב, הם למעשה מספרים [[מספר אקראי#מספר פסבדו אקראי|פסאודו-אקראיים]] המתקבלים באמצעות הפעלת פונקציה דטרמיניסטית על מספר התחלתי אקראי המכונה Seed. מספרים אלה נחשבים אקראיים לכל שימוש מעשי אך הם למעשה סדרה דטרמיניסטית. כדי להבטיח קבלת סדרה פסאודו-אקראית שונה בכל הרצה של התוכנית, על ה-Seed שבו היא משתמשת להגיע ממקור חיצוני לה שישתנה בין הרצות שונות - לרוב משתמשים בשעון של המחשב, או במידע על נתון "אקראי" כדוגמת הזזות העכבר של המשתמש. בנוסף לכך למחשב יכולה להיות גישה למספרים אקראיים "אמיתיים" על ידי חיבור להתקן מדידה פיזיקלי המודד תהליך אקראי (כמו התפרקות [[רדיואקטיבי|רדיואקטיבית]]ת).

אף על פי שכל בעיה אלגוריתמית פתירה, ניתנת לפתרון באמצעות אלגוריתם דטרמינסטי, בעבור חלק גדול מהבעיות האלגוריתמים הדטרמניסטיים הידועים איטיים יותר (במונחי [[סיבוכיות]]) ממשפחות אלגוריתמיות אחרות‏‏אחרות{{הערה|1=להרחבה בנושא זה ע"ע [[P=NP]]‏}}. ב[[תורת הסיבוכיות]] המחלקה המכילה את הבעיות שקיים אלגוריתם דטרמיניסטי הרץ בזמן סביר (פורמלית, זמן הריצה שלו הוא [[פולינום]] של גודל הקלט) מכונה [[P (סיבוכיות)|P]]. עם זאת, מכיוון שמחשבים מסוגלים להשתמש בפועל באקראיות בחישובים (באמצעות מחולל פסאודו אקראי), המושג של אלגוריתם דטרמיניסטי יעיל אינו מייצג את כלל השיטות היעילות לפתרון בעיות; המחלקה [[BPP]] המייצגת את כל הבעיות הניתנות לפתרון בידי אלגוריתם אקראי יעיל בעל הסתברות "טובה" להצלחה נחשבת על פי רוב למחלקה הסטנדרטית של "כל הבעיות הניתנות לפתרון יעיל במחשבים".

כיום ידועות מספר בעיות שלא מוכר אלגוריתם יעיל הפותר אותן, אך בהינתן מידע נוסף הן ניתנות לפתרון יעיל, מה שפותח פתח לשימוש בבעיות אלו כבסיס למערכות הצפנה. הדוגמה הקלאסית היא של מערכת ה[[הצפנה]] [[RSA]], שבה כדי לפענח הודעה יש לבצע חישוב התלוי במספר שהוא מכפלת שני [[ראשוני|ראשוניים]]ים גדולים. אם שני הראשוניים הללו ידועים קל לבצע את החישוב שמפענח הודעה; אך לא ידועה שום דרך לבצע חישוב זה ביעילות אם הם אינם ידועים, כך שקשה לתוקף לפצח את ההודעה (המתקפה הישירה ביותר דורשת [[פירוק לגורמים של מספר שלם|לפרק לגורמים]] את המכפלה, אך גם זוהי בעיה שנחשבת כיום לקשה). באופן כללי פונקציות שקל לחשב אך קשה להפוך מבלי שיהיה נתון מידע נוסף נקראות "פונקציות מלכודת" (Trapdoor functions).