# BPP

### מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

במדעי המחשב, BPP (ראשי תיבות של Bounded-Error, Probabilistic, Polynomial Time) הינה מחלקת הבעיות שיש עבורן אלגוריתם אקראי עם זמן ריצה פולינומיאלי, אשר צודק בהסתברות "טובה": ההסתברות (על פני המטבעות שמטיל האלגוריתם) שהאלגוריתם עונה את התשובה הנכונה היא לפחות 2/3.

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

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

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

מקור: http://he.wikipedia.org../../../b/p/p/BPP_f159.html

קטגוריה: סיבוכיות

##### Views

- ערך
- שיחה
- גרסה נוכחית

##### קהילה

- שער הקהילה
- עזרה
- דלפק ייעוץ
- מזנון
- יצירת קשר
- ספר אורחים

##### חיפוש

##### שפות אחרות

- English
- Deutsch
- Français
- 日本語
- 한국어
- Русский