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

באופן פורמלי, מוגדר אלגוריתם אקראי כבעזרת [[מכונת טיורינג הסתברותית]]: [[מכונת טיורינג]] רגילה אשר בנוסף לסרטים הרגילים שלה יש לה גישה לסרט קלט נוסף אשר מכיל רצף של "0"-ים ו-"1"-ים, המייצגים סדרה של הטלות אקראיות [[מאורעות בלתי תלויים|בלתי תלויות]] של מטבעות. ניתן להגדיר פלט של מכונת טיורינג כנ"ל כ[[התפלגות]] על פלטי המכונה בהינתן [[התפלגות אחידה]] בלתי תלויה של איברי סדרת הסרט הנוסף. פורמלית, [[סיבוכיות זמן ריצה|זמן הריצה]] של אלגוריתם אקראי הינו [[משתנה מקרי]], ולרובולעתים נמדדת יעילות האלגוריתם על פי [[תוחלת]] זמן הריצה שלו.