מכונת טיורינג הסתברותית

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

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

קיימות מספר דרכים שונות להגדיר מכונת טיורינג הסתברותית. רוב הדרכים שקולות או שאינן מוסיפות למכונה כוח משמעותי.

כל ההגדרות מתבססות על המודל הרגיל של מכונת טיורינג, אך מוסיפות לו כוח נוסף:

• הגדרה אחת מאפשרת למכונה לבחור בכל צעד בין שתי אפשרויות פעולה שונות, בהסתברות 1/2 לכל אחת מהן. הגדרה זו דומה להגדרת מכונת טיורינג אי דטרמיניסטית, שגם בה מאפשרים שני צעדים שונים בכל שלב. ניתן להכליל את ההגדרה כך שבכל שלב ניתן יהיה להגריל אחת מתוך n אפשרויות שונות (כאשר n הוא מספר קבוע המאפיין את המכונה) מבלי להוסיף לה כוח משמעותי.
• הגדרה נוספת מתבססת על מכונה דטרמיניסטית בעלת סרט אחד נוסף: "סרט האקראיות". בתחילת פעולתה של המכונה, הסרט מתמלא בצורה אקראית (בהתפלגות אחידה בדידה) ב0 ו-1 (ובהכללה, בכל האותיות שבא"ב של המכונה). לאחר מכן פעולת המכונה היא דטרמיניסטית לחלוטין, אך שימוש בסרט האקראיות מכניס אלמנט הסתברותי לפעולת המכונה.
• עוד הגדרה מבוססת על מתן אפשרות "כתיבה" חדשה למכונה, כאשר כתיבה זו היא של ביט אקראי - או 0 או 1 - בהתפלגות אחידה.

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

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

• המחלקה PP היא מחלקת כל בעיות ההכרעה שקיימת מכונה הסתברותית שפותרת אותן בזמן פולינומי וטועה בהסתברות קטנה מ-1/2. מחלקה זו היא רחבה למדי (למשל, היא מכילה את NP, ובעזרת אורקל אליה ניתן לפתור את כל הבעיות בהיררכיה הפולינומית). עם זאת, אין בה תועלת מעשית רבה שכן לא עבור כל הבעיות שבה ניתן להקטין את הסתברות השגיאה כמעט לאפס על ידי מספר סביר (פולינומי) של הפעלות חוזרות ונשנות של המכונה הפותרת אותן.
• המחלקה BPP היא מחלקת כל בעיות ההכרעה שקיימת מכונה הסתברותית שפותרת אותן בזמן פולינומי וטועה בהסתברות קטנה מ-1/3 (ניתן לבחור מספר אחר הקטן מ-1/2). מחלקה זו מוכלת ב-PP, אך יתרונה בכך שעל ידי מספר פולינומי של הפעלות חוזרות ונשנות של המכונה ניתן להקטין את הסתברות השגיאה עוד ועוד, עד שתשאף לאפס. BPP נחשבת למחלקה שמייצגת את כל מה שניתן להבין כחישובים הסתברותיים פרקטיים (כלומר - מהירים מספיק, ועם שגיאה זניחה), ולכן גם בתור המחלקה שתופסת בצורה הכללית ביותר את הבעיות שניתנות לפתרון פרקטי (שכן היא מכילה גם את P).
• המחלקות RP ו-Co-RP דורשות, בנוסף לזמן ריצה פולינומי, כי הטעות תהיה "חד צדדית" - בעיה היא ב-RP אם ניתן לפתור אותה בעזרת מכונת טיורינג הסתברותית כך שהיא מזהה כל פתרון שגוי (ההסתברות שתחזיר עליו תשובה שלילית היא 1) וטועה עבור פתרון נכון בהסתברות 1/2. Co-RP מוגדרת בצורה דומה, כאשר הטעות מותרת עבור פתרון שגוי ואסור לטעות עבור פתרון נכון.
• המחלקה ZPP היא מחלקת כל הבעיות שקיימת עבורן מכונה הסתברותית שאינה טועה כלל. עם זאת, למכונה זו מותר לרוץ גם בזמן שאינו פולינומי, והדרישה היא שתוחלת זמן הריצה תהיה פולינומית. סוג כזה של אלגוריתמים הסתברותיים מכונה אלגוריתמי לאס-וגאס.

בצורה דומה להגדרות המחלקות הללו ניתן גם להגדיר מחלקות מקבילות עבור דרישת זיכרון לוגריתמי. המחלקות המתקבלות מסומנות ב-PL,BPL,RL,Co-RL,ZPL.