RP – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־19:29, 26 בדצמבר 2015

במדעי המחשב, RP (ראשי התיבות של Randomized Polynomial time) היא מחלקת הסיבוכיות של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי בגודל הקלט באופן הבא:

אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
אם הקלט אינו בשפה, האלגוריתם דוחה.

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

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

אם התשובה הנכונה היא "כן" והאלגוריתם מורץ n פעמים, כאשר תוצאת כל ריצה היא בלתי תלויה סטטיסטית באחרות, הוא יחזיר "כן" לפחות פעם אחת בהסתברות של לפחות $1-2^{-n}$ . אז אם האלגוריתם מורץ 100 פעמים, ההסתברות שיענה תשובה שגויה נמוכה יותר מההסתברות שקרניים קוסמיות ישבשו את זיכרון המחשב שמריץ את האלגוריתם. מחלקת הסיבוכיות המשלימה ל- RP קרויה co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות BPP, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.

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

@@ שורה 1: / שורה 1: @@
-ב[[מדעי המחשב]], '''RP''' (ראשי התיבות של Randomized Polynomial time) היא המחלקה של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומי]] באופן הבא:
+ב[[מדעי המחשב]], '''RP''' (ראשי התיבות של Randomized Polynomial time) היא מחלקת הסיבוכיות של כל הבעיות הניתנות להכרעה הסתברותית ב[[זמן פולינומי]] בגודל הקלט באופן הבא:
 # אם הקלט בשפה, האלגוריתם מקבל בהסתברות של לפחות 1/2.
 # אם הקלט אינו בשפה, האלגוריתם דוחה.
+במילים אחרות, האלגוריתם יכו להטיל מטבע בעת ריצתו. המקרה היחידי שבו האלגוריתם מחזיר "כן" הוא אם התשובה היא באמת "כן". לכן, אם האלגוריתם מסיים ועונה "כן", אז התשובה היא בהכרח "כן". עם זאת, האלגוריתם עלול להשיב "לא" וזו תהיה תשובה שגויה.
-מחלקת הסיבוכיות המשלימה ל- RP קרויה '''co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות [[BPP]], הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
+יש המכנים את המחלקה R, אך שם זה שגור יותר עבור שפות רקורסיביות.
+אם התשובה הנכונה היא "כן" והאלגוריתם מורץ n פעמים, כאשר תוצאת כל ריצה היא בלתי תלויה סטטיסטית באחרות, הוא יחזיר "כן" לפחות פעם אחת בהסתברות של לפחות <math>1-2^{-n}</math>. אז אם האלגוריתם מורץ 100 פעמים, ההסתברות שיענה תשובה שגויה נמוכה יותר מההסתברות שקרניים קוסמיות ישבשו את זיכרון המחשב שמריץ את האלגוריתם.
+<references />מחלקת הסיבוכיות המשלימה ל- RP קרויה '''co-RP''', והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות [[BPP]], הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
 {{קצרמר|מחשבים}}