ZPP

במדעי המחשב, ZPP (ראשי תיבות של Zero-Error, Probabilistic, Polynomial Time.) הוא שמה של מחלקת סיבוכיות, שאחת מהגדרותיה המקובלת היא כמחלקת כל בעיות ההכרעה עבורן קיימת מכונת טיורינג הסתברותית שתמיד מחזירה תשובה נכונה, ותוחלת זמן הריצה שלה היא פולינומית. במילים אחרות, זוהי מחלקת כל הבעיות עבורן קיים אלגוריתם לאס וגאס אשר פותר אותן.

מבוא

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

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

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

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

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

ל-ZPP קיימות כמה הגדרות שונות ושקולות:

תוחלת זמן ריצה

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

מכונה עם אפשרות שלישית לתשובה

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

חיתוך RP ו-co-RP

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

מכאן קל לראות שהחיתוך מוכל בZPP: בהינתן בעיה בחיתוך, אלגוריתם ZPP עבורה מתבסס על הפעלת אלגוריתם ה-RP של הבעיה עבורה, ואחר כך הפעלת אלגוריתם ה-Co-RP שלה. אם אלגוריתם ה-RP ענה "כן", ניתן לענות "כן". אם אלגוריתם ה-RP ענה "לא" יש להפעיל את אלגוריתם ה-Co-RP. אם הוא ענה "לא" ניתן לענות "לא", ואחרת יש להפעיל את התהליך שוב. מובטח כי תתקבל תשובה נכונה בתוחלת זמן ריצה פולינומי.