אלגוריתם אקראי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Orielno Bot (שיחה | תרומות) מ clean up, replaced: התפלגות אחידה ← התפלגות אחידה בדידה באמצעות AWB |
←משפחות של אלגוריתמים אקראיים: שיפור מילולי תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד |
||
שורה 12:
* מחלקת הסיבוכיות '''[[ZPP]]''' מתארת את מכלול הבעיות אשר ניתן לפתור באמצעות אלגוריתם אקראי [[אלגוריתם יעיל|יעיל]] שאינו טועה (דהיינו, אלגוריתמי לאס וגאס).
* מחלקת הסיבוכיות '''[[RP]]''' מייצגת בעיות אשר יש עבורן [[אלגוריתם יעיל]] אקראי שעונה תמיד נכון על קלטים שהתשובה הנכונה עבורם היא "לא", אך עלול לטעות עבור קלטים שהתשובה הנכונה עבורם היא "כן".
* המחלקה '''[[Co-RP]]''' מייצגת בעיות אשר יש עבורן אלגוריתם יעיל אקראי שעונה תמיד נכון על קלטים שהתשובה הנכונה עבורם היא "כן", אך עלול
* מחלקת הסיבוכיות '''[[BPP]]''' מייצגת בעיות אשר יש עבורן אלגוריתם יעיל אקראי שעלול לטעות הן עבור קלטים שהתשובה הנכונה עבורם היא "כן" והן עבור קלטים שהתשובה הנכונה עבורם היא "לא". עם זאת, נדרש שהטעות תהיה כזו שמאפשרת הקטנה שלה על ידי הפעלות חוזרות ונשנות של האלגוריתם. לרוב מגדירים את המחלקה עם דרישת שגיאה של לכל היותר 1/3, אולם לכל בעיה במחלקה ניתן למצוא אלגוריתם יעיל אקראי שהשגיאה שלו קטנה באופן שרירותי.
* מחלקת הסיבוכיות '''[[PP]]''' מייצגת בעיות אשר יש עבורן אלגוריתם יעיל אקראי שעלול לטעות הן עבור קלטים שהתשובה הנכונה עבורם היא "כן" והן עבור קלטים שהתשובה הנכונה עבורם היא "לא", אך להבדיל מ-BPP ההסתברות לשגיאה יכולה להיות קרובה בצורה שרירותית לחצי, וכאשר התשובה הנכונה היא "לא" היא אף יכולה להיות שווה לחצי. בשל כך, PP היא מחלקה רחבה יותר מאשר BPP, אך לעומת זאת אם בעיה שייכת ל-PP זה אינו מבטיח שניתן יהיה למצוא לה אלגוריתם יעיל אקראי בעל הסתברות שגיאה קטנה באופן שרירותי.
| |||