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

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

 

*המחלקה [[BPP]] היא מחלקת כל בעיות ההכרעה שקיימת מכונה הסתברותית שפותרת אותן בזמן פולינומי וטועה בהסתברות קטנה מ-1/3 (ניתן לבחור מספר אחר הקטן מ-1/2). מחלקה זו מוכלת ב-PP, אך יתרונה בכך שעל ידי מספר פולינומי של הפעלות חוזרות ונשנות של המכונה ניתן להקטין את הסתברות השגיאה עוד ועוד, עד ש[[גבול (מתמטיקה)|תשאף לאפס]]. BPP נחשבת למחלקה שמייצגת את כל מה שניתן להבין כחישובים הסתברותיים פרקטיים (כלומר - מהירים מספיק, ועם שגיאה זניחה), ולכן גם בתור המחלקה שתופסת בצורה הכללית ביותר את הבעיות שניתנות לפתרון פרקטי (שכן היא מכילה גם את [[P (סיבוכיות)|P]]).

*המחלקות [[RP]] ו-[[Co-RP]] דורשות, בנוסף לזמן ריצה פולינומי, כי הטעות תהיה "חד צדדית" - בעיה היא ב-RP אם ניתן לפתור אותה בעזרת מכונת טיורינג הסתברותית כך שהיא מזהה כל פתרון שגוי (ההסתברות שתחזיר עליו תשובה שלילית היא 1) וטועה עבור פתרון נכון בהסתברות 1/2. Co-RP מוגדרת בצורה דומה, כאשר הטעות מותרת עבור פתרון שגוי ואסור לטעות עבור פתרון נכון.