אלגוריתם אקראי – הבדלי גרסאות

* '''[[שיטת מונטה קרלו|אלגוריתמי מונטה קרלו]]''' הינם אלגוריתמים אשר עלולים להחזיר תשובה לא נכונה לבעיה. דוגמה ידועה לאלגוריתם ממין זה הוא [[אלגוריתם מילר-רבין]] ל[[בדיקת ראשוניות]] של מספר. כאשר קלט נתון הוא מספר ראשוני, האלגוריתם תמיד יזהה אותו נכונה ככזה, אך האלגוריתם עלול גם לזהות [[מספר פריק]] כמספר ראשוני בהסתברות מסוימת. על ידי חזרה על האלגוריתם מספר רב של פעמים, ניתן להקטין את הסתברות השגיאה למספר קטן כרצוננו, אך לא להבטיח תשובה נכונה בוודאות מלאה. אלגוריתם זה, שנוצר בשנת [[1976]], הוא ראשיתו של תחום האלגוריתמים האקראיים.

 

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

* מחלקת הסיבוכיות '''[[RP]]''' מייצגת בעיות אשר יש עבורן [[אלגוריתם יעיל]] אקראי שעונה תמיד נכון על קלטים שהתשובה הנכונה עבורם היא "לא", אך עלול לטעות עבור קלטים שהתשובה הנכונה עבורם היא "כן".