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

קיימים יישומים בהם לא רוצים שהמצבים הבאים יהיו צפויים (כמתחייב מההגדרה). משחקי קלפים למשל הם דוגמה ליישום בו לא ניתן לתת את האפשרות לחזות את הקלפים הבאים בחפיסה. כיווןמכיוון שמחשביםשהאקראיות אינםשבה יכוליםהמחשב לייצרמשתמש מספריםאינה אקראייםאקראיות "אמיתית" אלא ניפוח דטרמיניסטי של Seed שעשוי להגיע ממקור בעל חוקיות מסויימת (בפרט, שעון המחשב), לא ניתן לגלותלמנוע באופן מוחלט מפעולת המחשב מלהיות צפויה עבור מהםמי הקלפיםשמנסה שיחולקולנתחה.

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