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

 

==הגדרה פורמלית==

==מחלקות סיבוכיות הסתברותיות==

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

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

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